package com.wm.algorithm.array;

import java.util.*;

/**
 * @ClassName: MediumArray
 * @Description: 中等级别
 * @Author: WM
 * @Date: 2021-07-24 23:07
 **/
public class MediumArray {

    public static void main(String[] args) {
        String a = "the sky is blue";
        System.out.println(a.substring(0, 2));
    }

    /**
     * 57. 插入区间
     * https://leetcode.cn/problems/insert-interval/description/
     * 方法：遍历
     * 思路：区间问题考虑的就是首位的元素值，因为题目给定的是排好序的区间列表了，所以取出给定插入区间的首尾元素值，
     * 然后遍历给定的区间集合，在遍历的过程中先去判断给定的目标区间是不是在遍历的当前区间的左侧或者是右侧，然后就是相交的情况，
     * 相交的情况也好处理，直接取出两个区间的最小元素值和最大元素值就好了
     *
     * @param intervals
     * @param newInterval
     * @return
     */
    // O(n)/O(1)
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0], right = newInterval[1];
        List<int[]> res = new ArrayList<>();
        boolean place = false;
        for (int[] interval : intervals) {
            // 判断目标区间是否在左侧
            if (interval[0] > right) {
                if (!place) {
                    res.add(new int[]{left, right});
                    place = true;
                }
                res.add(interval);
            } else if (left > interval[1]) {
                // 判断目标区间是否在右侧，直接加入当前区间就可以了，目标区间进行下一轮的比较
                res.add(interval);
            } else {
                // 相交，直接取出两个区间的最小元素值和最大元素值构成合并区间即可
                // 注意：这里不要加入结果集，他就处理一个区间！！！
                left = Math.min(interval[0], left);
                right = Math.max(interval[1], right);
            }
        }
        if (!place) {
            res.add(new int[]{left, right});
        }
        int[][] resTurn = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            resTurn[i] = res.get(i);
        }
        return resTurn;
    }

    /**
     * 969. 煎饼排序
     * https://leetcode.cn/problems/pancake-sorting/description/
     * 方法：选择排序+递归
     * 思路：先找到序列中最大值的索引位置，然后将到这个位置的子数组的元素进行反转，即将最大值反转到最上面。
     * 然后反转整个数组，将这个最大值放置数组的末端位置。然后这个元素固定在这个位置就不动了，继续递归处理剩下的n-1个元素
     * 注意：翻一次饼就是整个子数组的元素的反转一次
     *
     * @param arr
     * @return
     */
    // O(n^2)O(1)
    List<Integer> res2 = new ArrayList<>();

    public List<Integer> pancakeSort(int[] arr) {
        sort(arr, arr.length);
        return res2;
    }

    private void sort(int[] arr, int n) {
        // base case 就一个饼不需要反转了
        if (n == 1) {
            return;
        }
        // 寻找最大饼的索引
        int maxCase = 0, maxCaseIndex = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > maxCase) {
                maxCase = arr[i];
                maxCaseIndex = i;
            }
        }
        // 第一次翻转，将最大饼翻到最上面
        traverse(arr, 0, maxCaseIndex);
        res2.add(maxCaseIndex + 1);
        // 第一次翻转，将最大饼翻到最上面，固定了末位的元素，此处n-1
        traverse(arr, 0, n - 1);
        res2.add(n);

        // 递归调用
        sort(arr, n - 1);
    }

    private void traverse(int[] arr, int i, int j) {
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    /**
     * 659. 分割数组为连续子序列
     * https://leetcode.cn/problems/split-array-into-consecutive-subsequences/description/
     * 方法：贪心算法
     * 思路：定义两个map集合，freq:一个记录每个元素出现的次数，need:一个用于记录哪些元素可以追加到子序列的后面。
     * 首先遍历数组将元素对应出现的频次存储带freq集合中，然后遍历给定的数组，在遍历的过程中判断该元素是否是need集合中有的，
     * 有的话表示可以追加到子序列的后面，变更两个集合。如果不是，判断freq集合中是否有连续3元素的子序列，有的话就直接让当前元素
     * 作为新的子序列的头，否则就是没有可匹配的。
     * 这里需要注意当前遍历的元素能够追加到子序列就追加，不能追加再作为一个新的子序列开头，这样才能达到最优解。
     *
     * @param nums
     * @return
     */
    // O(n)/O(n)
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();
        // 统计 nums 中元素的频率
        for (Integer num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        for (Integer num : nums) {
            if (freq.get(num) == 0) {
                // 当前元素已经被用到其他子序列中
                continue;
            }
            // 先判断 num 是否能接到其他子序列后面
            if (need.containsKey(num) && need.get(num) > 0) {
                // num 可以接到之前的某个序列后面
                // 对 num 的需求减一
                freq.put(num, freq.get(num) - 1);
                // 对need的需求减1
                need.put(num, need.get(num) - 1);
                // 对 num + 1 的需求加一
                Integer next = num + 1;
                need.put(next, need.getOrDefault(next, 0) + 1);
            } else if (freq.get(num) > 0 && (freq.containsKey(num + 1) && freq.get(num + 1) > 0) &&
                    (freq.containsKey(num + 2) && freq.get(num + 2) > 0)) {
                // 将 num 作为开头，新建一个长度为 3 的子序列 [num,num+1,num+2]
                freq.put(num, freq.get(num) - 1);
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                // 对 num + 3 的需求加一
                Integer next = num + 3;
                need.put(next, need.getOrDefault(next, 0) + 1);
            } else {
                // 两种情况都不符合，则无法分配
                return false;
            }
        }
        return true;
    }

    /**
     * LCR 074. 合并区间
     * https://leetcode.cn/problems/SsGoHC/
     * 方法：排序+遍历
     * 思路：首先将给定的数组集合的左端元素进行排序，这样对于相交的区间的最左端就是合并后的区间的最左端。
     * 取集合的第一个区间，添加到结果集中，然后遍历剩下的区间集合，取出结果集最后一个元素，让其右端的元素和
     * 当前遍历的区间的左端元素进行比较大小，如果前者>=后者表示有交集，然后更新成最大的右端元素值。
     * 否则不相交，直接加入结果集合中
     *
     * @param intervals
     * @return
     */
    public int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = res.get(res.size() - 1);
            int[] curRow = intervals[i];
            if (curRow[0] <= last[1]) {
                last[1] = Math.max(curRow[1], last[1]);
            } else {
                res.add(curRow);
            }
        }
        return res.toArray(new int[0][0]);
    }

    /**
     * 986. 区间列表的交集
     * https://leetcode.cn/problems/interval-list-intersections/
     * 方法：遍历
     * 思路：区间问题首先想到的是排序，这道题给定的两个集合已经是排好序的了。这里我们使用两个指针分别遍历两个集合的行。
     * (a1,a2)，(b1,b2)代表指针指向的两个区间，相交区间有四种情况，通过画图可以分析总结得出，假设两个相交的区间是(c1,c2)，
     * c1=max(a1,b1);c2=min(a2,b2)。
     * 相交的条件：a2>=b1 || b2>=a1
     * 指针前移：a2<b2 i++;a2>b2 j++
     *
     * @param firstList
     * @param secondList
     * @return
     */
    // O(m+n)/O(m+n)
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> res = new ArrayList<>();
        int i = 0, j = 0;
        while (i < firstList.length && j < secondList.length) {
            int a1 = firstList[i][0], a2 = firstList[i][1];
            int b1 = secondList[j][0], b2 = secondList[j][1];
            // 考虑相交的情况
            if (a2 >= b1 && b2 >= a1) {
                res.add(new int[]{Math.max(a1, b1), Math.min(a2, b2)});
            }
            // 指针移动
            if (a2 < b2) {
                i++;
            } else {
                j++;
            }
        }
        return res.toArray(new int[0][0]);
    }

    /**
     * 56. 合并区间
     * 方法：排序+遍历
     * 思路：首先给区间集合按照最左元素进行升序，合并区间的最左元素就是排好序的区间集合中第一个区间的最左元素，合并区间的
     * 最大元素只需要遍历除了第一个区间之外区间集合，找到相交区间集合中最大的区间末端元素。不相交的区间直接加入到结果集合
     * 中，进行下一轮的比较
     *
     * @param intervals
     * @return
     */
    // O(nlogn)/O(logn)
    public int[][] merge(int[][] intervals) {
        // 按区间的 start 升序排列
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            // 按区间的 start 升序排列
            int[] last = res.get(res.size() - 1);
            int[] curRow = intervals[i];
            if (last[1] >= curRow[0]) {
                // 处理相交的情况
                last[1] = Math.max(last[1], curRow[1]);
            } else {
                // 不相交，处理下一个待合并区间
                res.add(curRow);
            }
        }
        return res.toArray(new int[0][0]);
    }

    /**
     * 1288. 删除被覆盖区间
     * https://leetcode.cn/problems/remove-covered-intervals/description/
     * 方法：排序+遍历
     * 思路：将给定区间的最左元素进行升序排序，遇到相等的情况，按照末端元素倒序排列。取第一个区间
     * 循环遍历其他区间和他进行对比，对比方式就是使用两个变量left，right分别取出左右端的元素值。
     * 两个区间的对比分成三种情况：
     * 情况一：找到覆盖区间
     * 情况二：两个区间的部分重叠，将二者合并成一个大区间
     * 情况三：两个区间不相交
     *
     * @param intervals
     * @return
     */
    // O(nlogn)/O(logn)
    public int removeCoveredIntervals(int[][] intervals) {
        // 按照起点升序排列，起点相同时降序排列
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });

        // 记录合并区间的起点和终点
        int left = intervals[0][0], right = intervals[0][1];
        int res = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (left <= intervals[i][0] && right >= intervals[i][1]) {
                // 情况一，找到覆盖区间
                res++;
            } else if (right >= intervals[i][0] && right <= intervals[i][1]) {
                // 情况二，找到相交区间，合并
                right = intervals[i][1];
            } else if (right < intervals[i][0]) {
                // 情况三，完全不相交，更新起点和终点
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        return intervals.length - res;
    }

    /**
     * 241. 为运算表达式设计优先级
     * https://leetcode.cn/problems/different-ways-to-add-parentheses/
     * 方法：分治算法
     * 思路：分：将每个计算符作为分割点，对分割点两侧的表达式进行计算，其实就相当于给整个表达式在此分割点
     * 两边加括号增加优先级进行计算。治：将计算的左右两个表达式的子结果，合成原问题的结果，即两个子结果和分割点运算符
     * 结合结算，最终的结果存入集合list中。
     * 备忘录：分割点的左边和右边的计算结果可能在不断分隔的过程中就结算过了，为减少重复的计算，我们加一个备忘录
     * base case：递归终有一个结束条件，这里我们判断list.isEmpty()的结果，如果是空，表示没有运算符，也就是不走里面的
     * 运算符if的判断，说明表达式是一个数字，没有运算符就可以结束递归了。
     *
     * @param expression
     * @return
     */
    // O(n(logn+n^2))/O(m)
    // 备忘录
    Map<String, List<Integer>> memoMap = new HashMap<>();

    public List<Integer> diffWaysToCompute(String expression) {
        // 避免重复结算
        if (memoMap.containsKey(expression)) {
            return memoMap.get(expression);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            // 扫描算式 input 中的运算符
            if (c == '+' || c == '-' || c == '*') {
                /****** 分 ******/
                // 以运算符为中心，分割成两个字符串，分别递归计算
                // 注意：这里是i，截取的是从0开始i索引之前的字符串
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                /****** 分 ******/
                // 以运算符为中心，分割成两个字符串，分别递归计算
                // 左半边和右半边的计算结果子集进行组合
                for (int a : left) {
                    for (int b : right) {
                        if (c == '+') {
                            res.add(a + b);
                        } else if (c == '-') {
                            res.add(a - b);
                        } else if (c == '*') {
                            res.add(a * b);
                        }
                    }
                }
            }
        }
        if (res.isEmpty()) {
            res.add(Integer.parseInt(expression));
        }
        return res;
    }

    /**
     * 787. K 站中转内最便宜的航班
     * https://leetcode.cn/problems/cheapest-flights-within-k-stops/
     * 方法：动态规划
     * 思路：定义dp(int s,int t)：从起点 src 出发，t 步之内（一步就是一条边）到达节点 s 的最小路径权重，
     * k表示最多不能超过最大中转个数，A->B>C，中转了1次，走了2条线，每条线上表示权重。
     * 给定一个节点，需要知道是哪个节点指向了这个节点，还有就是二者之间的权重，这个被指向的节点叫做入度节点。
     * 因为一个节点可能有多个节点指向，所以入度节点对应一个节点集合，也就是指向他的节点集合，key:value  to->[from,price]
     * base case：s==src t==0
     * 消除重叠子问题：如果一个节点指向其他两个节点，那么这两个节点就有相同的一个入度节点，会产生重复的计算。由于dp中的目标节点s和步数约束k在变化，
     * 所以使用二维数组去避免重复计算。
     *
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    // O((m+n)k)：m 是数组 flights 的长度。状态的数量为 O(nk)
    // O(nk)
    // 哈希表记录每个节点的入度
    Map<Integer, List<int[]>> indegree;
    int src, dst;
    int[][] memo11;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        this.src = src;
        this.dst = dst;
        // 将中转站个数转换成边的条数
        k++;

        // 计算节点的入度
        indegree = new HashMap<>();
        for (int[] flight : flights) {
            int from = flight[0], to = flight[1], price = flight[2];
            indegree.putIfAbsent(to, new ArrayList<>());
            indegree.get(to).add(new int[]{from, price});
        }

        // 初始化备忘录 n个站点，就有n个起点；一个转站点==两条边==三个相连点
        memo11 = new int[n][k + 1];
        for (int[] row : memo11) {
            Arrays.fill(row, -1);
        }
        // 注意这里，是从终点开始。因为从后向前移动，分析的是前节点指向当前节点
        return dp9(dst, k);
    }

    // 从src出发，t步之内达到s的最小成本
    private int dp9(int s, int t) {
        // base case
        if (s == src) { // 起点
            return 0;
        }
        if (t == 0) { // 已经走完t步了
            return -1;
        }

        // 备忘录，避免重复计算
        if (memo11[s][t] != -1) {
            return memo11[s][t];
        }

        // 状态转移方程
        // 初始化为最大值，方便等会取最小值
        int res = Integer.MAX_VALUE;
        if (indegree.containsKey(s)) {
            // 分析n个节点指向当前入度节点
            for (int[] preNode : indegree.get(s)) {
                int from = preNode[0];
                int price = preNode[1];
                // 从src到相邻的入度节点所需的最短路径权重
                int subProblem = dp9(from, t - 1);
                // 跳过无解的情况
                if (subProblem != -1) {
                    res = Math.min(subProblem + price, res);
                }
            }
        }

        // 存入备忘录 如果还是初始值，说明此节点不可达
        memo11[s][t] = res == Integer.MAX_VALUE ? -1 : res;
        return memo11[s][t];
    }

    /**
     * 剑指 Offer II 099. 最小路径之和
     * https://leetcode.cn/problems/0i0mDW/
     * 方法：动态规划（自定向下-迭代）
     * 思路：定义dp函数表示到当前位置的最小路径和，状态转移方程：
     * Math.min(dp(i-1,j),dp(i,j-1))+grid[i][j]
     * base case: i==0 && j==0 直接返回grid[0][0]；i<0 || j<0 直接返回Integer.MAX_VALUE； 目的是保证取到的是上次结果，因为本次是无解的。
     * 备忘录：因为这个过程会存在重复计算的情况 (i-1,j) (i,j-1) 到 (i-1,j-1)，所以需要加备忘录排除掉重复计算的情况
     *
     * @param grid
     * @return
     */
    // O(m*n)/O(m*n)
    int[][] memo10;

    public int minPathSum3(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        memo10 = new int[m][n];
        for (int[] row : memo10) {
            Arrays.fill(row, -1);
        }
        return dp8(grid, m - 1, n - 1);
    }

    private int dp8(int[][] grid, int i, int j) {
        // base case 走到头了
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }
        if (memo10[i][j] != -1) {
            return memo10[i][j];
        }

        memo10[i][j] = Math.min(dp8(grid, i - 1, j), dp8(grid, i, j - 1)) + grid[i][j];
        return memo10[i][j];
    }

    /**
     * 64. 最小路径和
     * https://leetcode.cn/problems/minimum-path-sum/
     * 方法2：动态规划（自底向上）
     * 思路：定义dp函数，从左上角位置(0,0)走到位置(i,j)的最小路径和dp(grid,i,j)，
     * dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值，状态转移方程：
     * Math.min(dp7(grid, i - 1, j), dp7(grid, i, j - 1)) + grid[i][j]
     * base case: 因为还是由前一个状态值去得出当前状态值，所以此时需要处理边界i=0和j=0是的情况
     * 将全部状态值都放入到dp的二维数组中，最后取最后一个位置的值即可。
     *
     * @param grid
     * @return
     */
    // O(m*n)/O(m*n)
    public int minPathSum2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        // base case
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 64. 最小路径和
     * https://leetcode.cn/problems/minimum-path-sum/
     * 方法1：动态规划（推荐，自顶向下）
     * 思路：定义dp函数，从左上角位置(0,0)走到位置(i,j)的最小路径和dp(grid,i,j)，
     * dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值，状态转移方程：
     * Math.min(dp7(grid, i - 1, j), dp7(grid, i, j - 1)) + grid[i][j]
     * base case: i==0 && j==0 返回grid[0][0]  i<0 || j<0 取int的最大值 Integer.MAX_VALUE
     * 定义备忘录数组，排除掉重叠子问题
     *
     * @param grid
     * @return
     */
    // O(m*n)/O(m*n)
    // 备忘录
    int[][] memo9;

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        memo9 = new int[m][n];
        // 构造备忘录，初始值全部设为 -1
        for (int[] row : memo9) {
            Arrays.fill(row, -1);
        }
        return dp7(grid, m - 1, n - 1);
    }

    private int dp7(int[][] grid, int i, int j) {
        // base case
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }

        // 避免重复计算
        if (memo9[i][j] != -1) {
            return memo9[i][j];
        }

        // 将计算结果记入备忘录
        memo9[i][j] = Math.min(dp7(grid, i - 1, j), dp7(grid, i, j - 1)) + grid[i][j];
        return memo9[i][j];
    }

    /**
     * 714. 买卖股票的最佳时机含手续费
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
     * 方法2：动态规划+临时变量存储相邻状态
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 因为k是无限的，所以计算的结果值和k是无关的，考虑到有手续费，那么在买入购入股票的时候需要减去手续费
     * 状态转移方程：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
     * 因为当前结果值之和前一个状态的值有关系，不需要整个dp数组，只需要一个变量存储相邻的那个状态就可以了，这样可以把空间复杂度降低到O(1)
     *
     * @param prices
     * @param fee
     * @return
     */
    // O(n)/O(1)
    public int maxProfit6(int[] prices, int fee) {
        int n = prices.length;
        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_0 - prices[i] - fee, dp_1);
        }
        // 取最后一天将股票卖出的状态值
        return dp_0;
    }

    /**
     * 714. 买卖股票的最佳时机含手续费
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
     * 方法1：动态规划+状态机
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 因为k是无限的，所以计算的结果值和k是无关的，考虑到有手续费，那么在买入购入股票的时候需要减去手续费
     * 状态转移方程：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
     * 确定base case：
     * 当i=0时，dp[i][0] = 0; dp[i][1] = -prices[i]-fee
     * 当i=1时，dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); dp[i][1] = -prices[i]-fee,dp[i-1][1])
     *
     * @param prices
     * @param fee
     * @return
     */
    // O(n)/O(n)
    public int maxProfit5(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            // base case
            if (i == 0) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i] - fee;
                continue;
            }
            // 状态转移
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i] - fee, dp[i - 1][1]);
        }
        // 取最后一天卖出股票的利润
        return dp[n - 1][0];
    }


    /**
     * 309. 最佳买卖股票时机含冷冻期
     * 方法2：动态规划+变量存储相邻状态
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 因为k是无限的，所以计算的结果值和k是无关的，由于买入（除了第一次）之前有存在冷冻期的情况，所以0->1需要动i-2开始
     * 状态转移方程：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
     * 因为当前结果值之和前一个状态的值有关系，不需要整个dp数组，只需要一个变量存储相邻的那个状态就可以了，这样可以把空间复杂度降低到O(1)
     *
     * @param prices
     * @return
     */
    // O(n)/O(1)
    public int maxProfit4(int[] prices) {
        int n = prices.length;
        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        int dp_pre = 0;
        for (int i = 0; i < n; i++) {
            // 上一个状态值
            int temp = dp_0;
            // 当前状态值
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_pre - prices[i], dp_1);
            // 即将进入下一轮，temp将作为下一轮的上上个状态值
            dp_pre = temp;
        }
        // 取最后一次不持有股票的状态
        return dp_0;
    }

    /**
     * 309. 最佳买卖股票时机含冷冻期
     * 方法1：动态规划+状态机
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 因为k是无限的，所以计算的结果值和k是无关的，由于买入（除了第一次）之前有存在冷冻期的情况，所以0->1需要动i-2开始
     * 状态转移方程：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
     * 确定base case：
     * 当i=0时，dp[i][0] = 0; dp[i][1] = -prices[i]
     * 当i=1时，dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); dp[i][1] = -prices[i],dp[i-1][1])
     *
     * @param prices
     * @return
     */
    // O(n)/O(n)
    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            // base case1:
            if (i == 0) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            // base case2:
            if (i == 1) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
                continue;
            }
            // 状态转移方程
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // i-2：买入的前一天是冷冻期
            dp[i][1] = Math.max(dp[i - 2][0] - prices[i], dp[i - 1][1]);
        }
        // 取最后一天的利润值
        return dp[n - 1][0];
    }

    /**
     * 122. 买卖股票的最佳时机 II
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
     * 方法2：动态规划+变量存储相邻状态
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 因为k是无限的，所以计算的结果值和k是无关的，状态转移方程：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
     * 因为当前结果值之和前一个状态的值有关系，不需要整个dp数组，只需要一个变量存储相邻的那个状态就可以了，这样可以把空间复杂度降低到O(1)
     *
     * @param prices
     * @return
     */
    // O(n)/O(1)
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        // 持有和不持有股票的利润值（状态）   dp_1一定要去一个负数最小值，因为dp_1可能为负数
        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // 昨天的利润值
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(temp - prices[i], dp_1);
        }
        // 取最后一天的状态结果值
        return dp_0;
    }

    /**
     * 122. 买卖股票的最佳时机 II
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
     * 方法1：动态规划+状态机
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 因为k是无限的，所以计算的结果值和k是无关的，状态转移方程：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
     * 确定base case：
     * 当i=0时，dp[i][0] = 0; dp[i][1] = -prices[i]
     *
     * @param prices
     * @return
     */
    // O(n)/O(n)
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            // base case:
            if (i == 0) {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        // 取最后一天的状态结果值
        return dp[n - 1][0];
    }

    /**
     * 139. 单词拆分
     * 方法：动态规划
     * 思路：定义dp(s,i)为是s的前缀中是否可以匹配上word单词，i是匹配s前缀的一个单词在s中的索引。状态转移方程：在给定的单词集合
     * 中有单词可以是s的前缀部分，此时下一个状态是从匹配了单词的下一个位置去继续寻找，直到i==s.length()。个人理解就是截取s中的单词去匹配
     * word集合中的单词，一直遍历到s的完毕还能匹配上就是找到了，因为只有保证上一个部分片段匹配上才能进行下一次的匹配。
     * base case：i==s.length()
     * 使用备忘录消除重叠子问题
     *
     * @param s
     * @param wordDict
     * @return
     */
    // O(m^3)/O(n)  m:s的长度  n:wordDict个数
    // 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
    int[] memo8;
    // 用哈希集合方便快速判断是否存在
    Set<String> wordSet = null;

    public boolean wordBreak(String s, List<String> wordDict) {
        // 备忘录初始化为 -1
        memo8 = new int[s.length()];
        Arrays.fill(memo8, -1);
        // 转化为哈希集合，快速判断元素是否存在
        wordSet = new HashSet<>(wordDict);
        return dp6(s, 0);
    }

    // 定义：s[i..] 是否能够被拼出
    private boolean dp6(String s, int i) {
        // base case
        if (i == s.length()) {
            return true;
        }
        // 防止冗余计算
        if (memo8[i] != -1) {
            return memo8[i] == 1;
        }
        // 遍历 s[i..] 的所有前缀  注意这里的取值，len=1，中间的条件是<=
        for (int len = 1; i + len <= s.length(); len++) {
            // 看看哪些前缀存在 wordDict 中
            String prefix = s.substring(i, i + len);
            if (wordSet.contains(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                // 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出
                boolean subProblem = dp6(s, i + len);
                if (subProblem) {
                    memo8[i] = 1;
                    return true;
                }
            }
        }
        // s[i..] 无法被拼出
        memo8[i] = 0;
        return false;
    }

    /**
     * 剑指 Offer II 090. 环形房屋偷盗
     * https://leetcode.cn/problems/PzWKhm/
     * 方法：动态规划
     * 思路：确定状态和选择：前面的房子的索引是状态，抢和不抢是选择，当前的房子不抢就去下家，抢就选择下下家。
     * 本题因为是环形的房子，需要考虑到首尾房子是相连的，首尾二者选其一，取其中计算结果最大的值
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int rob5(int[] nums) {
        int n = nums.length;
        // 考虑到后面的n-2
        if (n == 1) {
            return nums[0];
        }
        return Math.max(rangeRob2(nums, 0, n - 2), rangeRob2(nums, 1, n - 1));
    }

    private int rangeRob2(int[] nums, int start, int end) {
        int dp_i = 0, dp_1 = 0, dp_2 = 0;
        for (int i = end; i >= start; i--) {
            dp_i = Math.max(nums[i] + dp_2, dp_1);
            dp_2 = dp_1;
            dp_1 = dp_i;
        }
        return dp_i;
    }

    /**
     * 剑指 Offer II 089. 房屋偷盗
     * 方法：动态规划
     * 思路：首先确定状态和选择：前面的房子的索引是状态，抢和不抢是选择，当前的房子不抢就去下家，抢就得下下家。
     * 实现就是从给定的数组后面向前遍历（因为涉及到下下个索引，所以使用从后向前进行遍历），状态转移只和最近的
     * 两个状态有关系，所以可以用变量记录三个状态转移的值。这样将空间复杂度从O(n)降到O(1)
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int rob4(int[] nums) {
        int dp_i = 0;
        // 状态1是选择当前房子，状态2不选当前房子的金额获取总值
        int dp_1 = 0, dp_2 = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            // 状态转移：决策是否选择当前房子，选择金额最大的结果
            dp_i = Math.max(nums[i] + dp_2, dp_1);
            dp_2 = dp_1;
            dp_1 = dp_i;
        }
        return dp_i;
    }

    /**
     * 213. 打家劫舍 II
     * 方法：动态规划
     * 思路：首先确定状态和选择：前面的房子的索引就是状态，抢和不抢是选择。当前的房子不抢就去下家，抢就得抢下下家。
     * 其实，说白了就是从数组的后面向前进行遍历，状态转移只和最近的两个状态有关系，所以可以用变量就记录三个状态转移的值。
     * 这样将空间复杂度从O(n)降到了O(1)
     * 在打家劫舍I的前提下，决策选择首不选择尾，不选择首选择尾的最优解的情况。
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int rob3(int[] nums) {
        int n = nums.length;
        // 注意这里的条件
        if (n == 1) {
            return nums[0];
        }
        return Math.max(rangeRob(nums, 0, n - 2), rangeRob(nums, 1, n - 1));
    }

    // 仅计算闭区间 [start,end] 的最优结果
    private int rangeRob(int[] nums, int start, int end) {
        int dp_1 = 0, dp_2 = 0;
        int dp_i = 0;
        for (int i = end; i >= start; i--) {
            dp_i = Math.max(nums[i] + dp_2, dp_1);
            dp_2 = dp_1;
            dp_1 = dp_i;
        }
        return dp_i;
    }

    /**
     * 198. 打家劫舍
     * 方法2：动态规划【自底向上】
     * 思路：首先确定状态和选择：前面的房子的索引就是状态，抢和不抢是选择。当前的房子不抢就去下家，抢就得抢下下家。
     * 其实，说白了就是从数组的后面向前进行遍历，状态转移只和最近的两个状态有关系，所以可以用变量就记录三个状态转移的值。
     * 这样将空间复杂度从O(n)降到了O(1)
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int rob2(int[] nums) {
        int n = nums.length;
        // 记录 dp[i+1] 和 dp[i+2]
        int dp_1 = 0, dp_2 = 0;
        // 记录 dp[i]
        int dp_i = 0;
        for (int i = n - 1; i >= 0; i--) {
            dp_i = Math.max(nums[i] + dp_2, dp_1);
            // 状态值前进滚动更新
            dp_2 = dp_1;
            dp_1 = dp_i;
        }
        return dp_i;
    }

    /**
     * 198. 打家劫舍
     * 方法1：动态规划【自顶向下】
     * 思路：首先确定状态和选择：前面的房子的索引就是状态，抢和不抢是选择。当前的房子不抢就去下家，抢就得抢下下家。
     * 同一个位置会出现重叠的情况，所以还需要使用备忘录进行排重。
     *
     * @param nums
     * @return
     */
    // O(n)/O(n)
    int memo7[];

    public int rob(int[] nums) {
        // 初始化备忘录
        memo7 = new int[nums.length];
        Arrays.fill(memo7, -1);
        // 强盗从第0间房子开始抢劫
        return dp5(nums, 0);
    }

    // 返回 dp[start..] 能抢到的最大值
    private int dp5(int[] nums, int start) {
        // base case
        if (start >= nums.length) {
            return 0;
        }
        // 避免重复计算
        if (memo7[start] != -1) {
            return memo7[start];
        }
        int res = Math.max(
                // 不抢，去下家
                dp5(nums, start + 1),
                // 抢，去下下家
                nums[start] + dp5(nums, start + 2));
        // 记入备忘录
        memo7[start] = res;
        return res;
    }

    /**
     * 516. 最长回文子序列
     * https://leetcode.cn/problems/longest-palindromic-subsequence/
     * 方法：动态规划
     * 思路：使用二维数组去解题，在子串s[i..j] 中，最长回文子序列的长度为dp[i][j]。个人理解为是两个指针的移动，两个指针之间的序列是
     * 回文串，从尾端左指针向前移动，每次固定左指针，然后右指针在当前位置向后移动，dp数组记录的就是指针当前状态的结果。判断两个位置的元素
     * 是不是相等的，如果相等两个指针前后分别移动，如果不相等移动二者指针其一取最大状态的结果。
     * 动态转移就是去更新这个回文串的长度。base case：1，同时。从末端往前移动的原因是动态转移的过程中涉及到
     * dp[i + 1][j - 1]、dp[i+1][j]、dp[i][j-1]三个状态
     *
     * @param s
     * @return
     */
    // O(n^2)/O(n^2)
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // base case：dp数组对角线初始化为1
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            // 初始化两个指针同时指向一个位置的值
            dp[i][i] = 1;
        }
        // 反着遍历保证正确的转移状态
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 状态转移方程
                if (s.charAt(j) == s.charAt(i)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        // 整个s的最长回文子串的长度
        return dp[0][n - 1];
    }

    /**
     * 1024. 视频拼接
     * https://leetcode.cn/problems/video-stitching/description/
     * 方法：贪心算法
     * 思路：对时间区间的起始节点进行升序处理，第一个时间区间的起点值必然是0，在遍历的过程中，筛选出时间区间末端值最大的，
     * 但是前提条件是当前时间区间的节点的起始值必须要<=上一个时间区间的末端值。这样才能保证两个视频可以首位连接起来
     * （多出来的片段可剪掉，少了就拼不起来了）
     *
     * @param clips
     * @param time
     * @return
     */
    // O(nlogn)/O()
    public int videoStitching(int[][] clips, int time) {
        if (time == 0) {
            return 0;
        }
        // 对数组的时间起点升序，解题作者说了使用相同起点相同，末端值倒序，其实是没必要的
        // 因为在遍历过程中都需要判断末端值和之前末端值的大小
        // 这里比较的时间复杂度是O(nlogn)
        Arrays.sort(clips, (o1, o2) -> o1[0] - o2[0]);

        int n = clips.length;
        int i = 0;
        int curEnd = 0, nextEnd = 0;
        // 记录选择的短视频个数
        int res = 0;
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个视频的区间内贪心选择下一个视频
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = Math.max(clips[i][1], nextEnd);
                // 起点相同会继续这个嵌套循环
                i++;
            }
            res++;
            // 找到下一个视频，更新 curEnd
            curEnd = nextEnd;
            if (curEnd >= time) {
                // 已经可以拼出区间 [0, T]
                return res;
            }
        }
        // 已经可以拼出区间 [0, T]
        return -1;
    }

    /**
     * 11. 盛最多水的容器
     * https://leetcode.cn/problems/container-with-most-water/
     * 方法：双指针
     * 思路：用left和right两个指针从两端向中心收缩，一边收缩一边计算[left, right]之间的矩形面积，取最大的面积值即是答案。
     *
     * @param height
     * @return
     */
    // O(n)/O(1)
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            // [left, right] 之间的矩形面积
            int area = Math.min(height[left], height[right]) * (right - left);
            res = Math.max(area, res);
            // 双指针技巧，移动较低的一边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }

    /**
     * 253. 会议室 II
     * https://leetcode.cn/problems/meeting-rooms-ii/
     * 方法：时间线扫描（双指针+贪心算法）
     * 思路：想想将会议的时间区间的断点都映射到一个时间线上，在这个时间线上从左向右进行扫描，
     * 遇到起始时间点（红点）计数器+1，遇到终止时间点（绿点）计数器-1，计数器的最大值就是最终的结果值。
     * 在实现上需要将给定数组中的会议时间的起始时间和终点时间分别进行排序，然后在进行遍历计数。
     *
     * @param meetings
     * @return
     */
    // O(n)/O(n)
    int minMeetingRooms(int[][] meetings) {
        int n = meetings.length;
        int[] begin = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < n; i++) {
            begin[i] = meetings[i][0];
            end[i] = meetings[i][1];
        }
        Arrays.sort(begin);
        Arrays.sort(end);
        // 扫描过程中的计数器
        int count = 0;
        // 双指针技巧
        int i = 0, j = 0, res = 0;
        while (i < n && j < n) {
            if (begin[i] < end[i]) {
                // 扫描到一个红点
                count++;
                i++;
            } else {
                // 扫描到一个绿点
                count--;
                j++;
            }
            // 记录扫描过程中的最大值
            res = Math.max(res, count);
        }
        return res;
    }

    /**
     * 45. 跳跃游戏 II
     * https://leetcode.cn/problems/jump-game-ii/
     * 方法：贪心算法
     * 思路：遍历整个数据，在起始位置计算出跳的最大位置，然后计算当前位置i到end区间的最大跳跃位置farthest，
     * 这里的计算过程处理的很精妙，在未达到end位置之前，在遍历过程中去更新farthest，当到达end之后，变更下一个
     * 最大跳跃的位置下标，并更新跳跃的次数。相当是计算每个子区间的最大跳跃位置，统计跳跃数。
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int jump(int[] nums) {
        int n = nums.length - 1;
        int farthest = 0;
        int end = 0;
        int jump = 0;
        for (int i = 0; i < n; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            // 达到跳跃子区间的末端
            if (end == i) {
                jump++;
                end = farthest;
            }
        }
        return jump;
    }

    /**
     * 55. 跳跃游戏
     * https://leetcode.cn/problems/jump-game/
     * 方法：贪心算法
     * 思路：遍历数组计算当前位置最远能够跳到哪里，然后和全局最优的最远位置进行对比，通过每一步的
     * 最优解更新全局的最优解
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public boolean canJump(int[] nums) {
        int n = nums.length - 1;
        int farthest = 0;
        for (int i = 0; i < n; i++) {
            // 不断计算能跳到的最远距离
            farthest = Math.max(farthest, i + nums[i]);
            // 可能碰到了 0，卡住跳不动了
            if (farthest <= i) {
                return false;
            }
        }
        return farthest >= n;
    }

    /**
     * 452. 用最少数量的箭引爆气球
     * https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
     * 方法：贪心算法
     * 思路：首先明确规则，边缘的值相等就算是重叠。计算出重叠子区间的个数：将给定的子区间集合的末端值end进行升序排序，
     * 遍历排好序的集合【排除掉去的第一个子区间】，对子区间的首位值begin>=end，进计数处理，最终这个计数的结果是无重
     * 叠子区间的最大个数。无重叠的子区间数量最大会使得射箭的数量最少。
     *
     * @param points
     * @return
     */
    // O(nlogn)/O(logn)
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        // 按 end 升序排序
        Arrays.sort(points, new Comparator<int[]>() {
            // 这里必须这么写，因为有负值的坐标，末端值是负的很大，减去末端值很大的正数会溢出。
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] > o2[1]) {
                    return 1;
                } else if (o1[1] < o2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        // 至少有一个区间不相交
        int count = 1;
        // 排序后，第一个区间就是 x，取第一个区间的末端值
        int xEnd = points[0][1];
        for (int i = 1; i < points.length; i++) {
            int start = points[i][0];
            // 注意这里，边缘值相同算是重叠，所以这个不使用=
            if (start > xEnd) {
                count++;
                // 更新末端值
                xEnd = points[i][1];
            }
        }
        return count;
    }

    /**
     * 435. 无重叠区间
     * https://leetcode.cn/problems/non-overlapping-intervals/
     * 方法：贪心算法
     * 思路：首先明确规则，边缘的值相等也不算是重叠。这种类型的题就可以类比开会安排，一个人不能参加含有重叠时间的会议。
     * 将给定的子区间集合的末端值end进行升序排序，遍历排好序的集合【排除掉去的第一个子区间】，对子区间的首位值begin>=end，进行
     * 计数处理，最终这个计数的结果是无重叠子区间的最大个数，题目要求的是获取至少移出的子区间数量。
     *
     * @param intervals
     * @return
     */
    // O(nlogn)/O(logn)
    // 时间复杂度：O(nlogn)，其中 n 是区间的数量。我们需要 O(nlogn) 的时间对所有的区间按照右端点进行升序排序，并且需要 O(n)
    // 的时间进行遍历。由于前者在渐进意义下大于后者，因此总时间复杂度为O(nlogn)。
    // 空间复杂度：O(logn)，即为排序需要使用的栈空间。
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        // 按 end 升序排序  都是正数，这里这么比较没问题
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        // 至少有一个区间不相交
        int count = 1;
        // 排序后，第一个区间就是 x，取第一个区间的末端值
        int xEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0];
            if (start >= xEnd) {
                count++;
                // 更新末端值
                xEnd = intervals[i][1];
            }
        }
        return intervals.length - count;
    }

    /**
     * 931. 下降路径最小和
     * https://leetcode.cn/problems/minimum-falling-path-sum/
     * 方法：动态规划
     * 思路：确定能走到当前位置元素matrix[i][j]的，是上一行的元素可以是：
     * matrix[i][j-1]、左上matrix[i-1][j-1]、右上matrix[i+1][j-1]。
     * 1.确定base case: i==0，直接返回当前值
     * 2.确定dp[][]：从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径的元素和为 dp(matrix,i,j)
     * 3.确定状态转移方式：三个到当前位置的和的最小值是当前的更新的状态结果，递归过程中索引合法性检测需要注意取范围之外的值
     * 4.使用备忘录避免重复计算。
     * 注意范围的选取：备忘录的初始值选取在给定值的范围之外即可：
     * matrix 的大小是 100 x 100，所有元素都是 100，那么从第一行往下落，得到的路径和就是 100 x 100 = 10000
     * 合法结果会落在区间 [-10000, 10000] 中
     *
     * @param matrix
     * @return
     */
    // O(n^2)/O(n^2)
    int memo6[][];

    public int minFallingPathSum(int[][] matrix) {
        // 可以确定给定的这个二维数组是个正方形
        int n = matrix.length;
        memo6 = new int[n][n];
        // 备忘录里的值初始化为 66666
        for (int[] row : memo6) {
            Arrays.fill(row, 66666);
        }
        // 遍历每一行，自最底层向上，自右向左遍历
        int res = Integer.MAX_VALUE;// 这里取数组可能取值范围外的值
        // 终点可能在 matrix[n-1] 的任意一列
        for (int j = 0; j < n; j++) {
            res = Math.min(res, dp4(matrix, n - 1, j));
        }
        return res;
    }

    private int dp4(int[][] matrix, int i, int j) {
        // 索引合法性检测，注意右、下边界的校验有=
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
            return 99999;
        }
        // base case，第一行直接返回
        if (i == 0) {
            return matrix[0][j];
        }
        // 检测备忘录，防止重复计算
        if (memo6[i][j] != 66666) {
            return memo6[i][j];
        }
        // 状态转移方程
        memo6[i][j] = matrix[i][j] + Math.min(dp4(matrix, i - 1, j - 1),
                Math.min(dp4(matrix, i - 1, j), dp4(matrix, i - 1, j + 1)));
        return memo6[i][j];
    }

    /**
     * 72. 编辑距离
     * https://leetcode.cn/problems/edit-distance/
     * 方法：动态规划
     * 思路：将两个字符串从后往前进行比对，以word1为标准，遇到相同字符不做操作，i与j都减1操作，遇到不相等的字符串需要进行增/删/替的操作，
     * 注意这里的操作都是针对word1来说的。
     * 删是在word2遍历完成word1还没遍历完的情况。增和替需要看具体的场景了，目的是寻找到最小的操作次数。这里就需要比较增/删/替最终的操作数最小值了。
     * 这里使用到了备忘录，目的是减少重复子问题。
     *
     * @param word1
     * @param word2
     * @return
     */
    // O(mn)/O(mn)
    int memo5[][];

    public int minDistance2(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // 备忘录初始化为特殊值，代表还未计算
        memo5 = new int[m][n];
        for (int[] row : memo5) {
            Arrays.fill(row, -1);
        }
        return dp4(word1, m - 1, word2, n - 1);
    }

    private int dp4(String word1, int i, String word2, int j) {
        if (i == -1) {
            return j + 1;
        }
        if (j == -1) {
            return i + 1;
        }
        // 查备忘录，避免重叠子问题
        if (memo5[i][j] != -1) {
            return memo5[i][j];
        }

        // 状态转移，结果存入备忘录
        if (word1.charAt(i) == word2.charAt(j)) {
            memo5[i][j] = dp4(word1, i - 1, word2, j - 1);
        } else {
            // 增  删
            int temp = Math.min(dp4(word1, i, word2, j - 1) + 1, dp4(word1, i - 1, word2, j) + 1);
            // 替
            memo5[i][j] = Math.min(temp, dp4(word1, i - 1, word2, j - 1) + 1);
        }
        return memo5[i][j];
    }

    /**
     * 712. 两个字符串的最小ASCII删除和
     * https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
     * 方法：动态规划+递归+备忘录
     * 思路：利用计算最长公共子序列的思路去做，只不过base case和状态转移部分需要修改，memo中存放的值改为存取的删除字符的ASCII码值。
     * base case:当其中的一个字符串遍历完成，那此时将另一个字符串剩下的字符需要全部删除
     * 状态转移:判断两个字符不相等的情况下，将memo中存储的值改为计算s1[i]，s[j]至少一个不在lcs删除字符的最小值
     *
     * @param s1
     * @param s2
     * @return
     */
    // 备忘录
    int[][] memo4;

    // O(mn)/O(mn)
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // 备忘录值为 -1 代表未曾计算
        memo4 = new int[m][n];
        for (int[] row : memo4) {
            Arrays.fill(row, -1);
        }
        return dp3(s1, 0, s2, 0);
    }

    // 定义：将 s1[i..] 和 s2[j..] 删除成相同字符串，
    // 最小的 ASCII 码之和为 dp(s1, i, s2, j)。
    private int dp3(String s1, int i, String s2, int j) {
        int res = 0;
        // base case
        if (i == s1.length()) {
            // 如果 s1 到头了，那么 s2 剩下的都得删除
            for (; j < s2.length(); j++) {
                res += s2.charAt(j);
            }
            return res;
        }
        if (j == s2.length()) {
            // 如果 s1 到头了，那么 s2 剩下的都得删除
            for (; i < s1.length(); i++) {
                res += s1.charAt(i);
            }
            return res;
        }
        if (memo4[i][j] != -1) {
            return memo4[i][j];
        }
        if (s1.charAt(i) == s2.charAt(j)) {
            // s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
            memo4[i][j] = dp3(s1, i + 1, s2, j + 1);
        } else {
            // s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
            memo4[i][j] = Math.min(dp3(s1, i + 1, s2, j) + s1.charAt(i),
                    dp3(s1, i, s2, j + 1) + s2.charAt(j));
        }
        return memo4[i][j];
    }

    /**
     * 583. 两个字符串的删除操作
     * https://leetcode.cn/problems/delete-operation-for-two-strings/
     * 方法：动态规划+递归+备忘录
     * 思路：此题可以转换成计算两个字符串的最长公共子序列的长度lcs，然后将两个字符串的长度分别减去lcs，然后加起来
     * 就是最终求得到的最小删除次数
     *
     * @param word1
     * @param word2
     * @return
     */
    int[][] memo3;

    // O(mn)/O(mn)
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // 计算两个字符串的最长公共子序列
        memo3 = new int[m][n];
        // 给备忘录赋值
        for (int[] row : memo3) {
            Arrays.fill(row, -1);
        }
        int lcs = dp2(word1, 0, word2, 0);
        return m - lcs + n - lcs;
    }

    private int dp2(String text1, int i, String text2, int j) {
        // base case
        if (text1.length() == i || text2.length() == j) {
            return 0;
        }
        if (memo3[i][j] != -1) {
            return memo3[i][j];
        }
        // 状态转移
        if (text1.charAt(i) == text2.charAt(j)) {
            memo3[i][j] = dp2(text1, i + 1, text2, j + 1) + 1;
        } else {
            memo3[i][j] = Math.max(dp2(text1, i + 1, text2, j), dp2(text1, i, text2, j + 1));
        }
        return memo3[i][j];
    }

    /**
     * 1143. 最长公共子序列
     * https://leetcode.cn/problems/longest-common-subsequence/
     * 文章参考：https://mp.weixin.qq.com/s/ZhPEchewfc03xWv9VP3msg
     * 方法：备忘录+动态规划+递归
     * 思路：使用两个指针i，j分别指向两个字符串，最长公共子序列的长度表示dp(s1,i,s2,j)，记录状态转移的结果。
     * base case为i=len(s1)或j=len(s2)，此时表示的就是没有找到公共的子串，所以结果直接为0。每一次递归先看备忘录中是否
     * 记录过，如果记录过直接返回，否则进行下面的字符对比处理，相等进行下一轮的字符对比，如果不是找到下一个状态的最大公共子序列的长度。
     *
     * @param text1
     * @param text2
     * @return
     */
    // O(mn)/O(mn)
    // 备忘录，消除重叠子问题
    int[][] memo2;

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        memo2 = new int[m][n];
        // 备忘录值为 -1 代表未曾计算
        for (int[] row : memo2) {
            Arrays.fill(row, -1);
        }
        // 计算 s1[0..] 和 s2[0..] 的 lcs 长度
        return dp(text1, 0, text2, 0);
    }

    // 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
    private int dp(String s1, int i, String s2, int j) {
        // base case
        if (i == s1.length() || j == s2.length()) {
            return 0;
        }
        // 如果之前计算过，则直接返回备忘录中的答案
        if (memo2[i][j] != -1) {
            return memo2[i][j];
        }
        // 根据 s1[i] 和 s2[j] 的情况做选择
        if (s1.charAt(i) == s2.charAt(j)) {
            // s1[i] 和 s2[j] 必然在 lcs 中
            memo2[i][j] = dp(s1, i + 1, s2, j + 1) + 1;
        } else {
            // s1[i] 和 s2[j] 至少有一个不在 lcs 中
            memo2[i][j] = Math.max(dp(s1, i + 1, s2, j), dp(s1, i, s2, j + 1));
        }
        return memo2[i][j];
    }

    /**
     * 53. 最大子数组和
     * https://leetcode.cn/problems/maximum-subarray/
     * 方法三：前缀和
     * 思路：前缀和数组preSum就是nums元素的累加和，preSum[i+1]-preSum[j]其实就是子数组nums[j...i]子数组元素之和
     * （根据preSum数组的实现，索引0是占位符，所以i有一位索引偏移）。以nums[i]为结尾的最大子数组之和=preSum[i+1]-min(preSum[0...i])，
     * 所以，我们可以利用前缀和数组计算以每个元素结尾的子数组之和，进而得到和最大的子数组
     *
     * @param nums
     * @return
     */
    // O(n)/O(n)
    public int maxSubArray3(int[] nums) {
        int n = nums.length;
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        int minVal = Integer.MAX_VALUE;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            minVal = Math.min(minVal, preSum[i]);
            res = Math.max(res, preSum[i + 1] - minVal);
        }
        return res;
    }

    /**
     * 剑指 Offer II 091. 粉刷房子
     * https://leetcode.cn/problems/JEj789/?show=1
     * 方法：动态规划
     * 思路：基础条件是第一个房子花费的费用，状态转移：第i个房子花费的费用和是前一个房子有关，更新总最少费用
     * （这一需要注意每个房子用同一个颜色的油漆花费的价格也是不同的，毕竟房子面积不一样嘛）
     *
     * @param costs
     * @return
     */
    //O(n)/O(n)
    public int minCost(int[][] costs) {
        // 房子数量
        int n = costs.length;
        // 定义：当第 i 个房子粉刷颜色 j 时，粉刷 [0..i] 这些房子所需的最少花费为 dp[i][j]
        // 其中 j = 0, 1, 2 分别代表三种颜色
        int[][] dp = new int[n][3];

        // base case 第一个房子花费的费用是固定的，设置每种颜色涂料所需要的费用
        for (int j = 0; j < 3; j++) {
            dp[0][j] = costs[0][j];
        }

        // 状态转移，穷举所有「选择」
        for (int i = 1; i < n; i++) {
            // 颜色0只能挨着颜色1或颜色2
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            // 颜色1只能挨着颜色0或颜色2
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
            // 颜色2只能挨着颜色0或颜色1
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
        }

        // 计算题目要求的结果
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < 3; j++) {
            res = Math.min(dp[n - 1][j], res);
        }
        return res;
    }

    /**
     * 53. 最大子数组和
     * https://leetcode.cn/problems/maximum-subarray/
     * 方法二：动态规划
     * 思路：确定基础条件：num[0]=0是结果初始值，确定状态转移方程，当前nums遍历的值，加上上一个遍历值的最大子数组和dp0与当前值比较大小，最大的值是更新
     * 后的状态值dp1。
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int maxSubArray2(int[] nums) {
        if (nums.length == 0) {
            return nums[0];
        }
        // base case
        int dp0 = nums[0];
        int dp1, res = dp0;
        // 注意这里i的值是从1开始
        for (int i = 1; i < nums.length; i++) {
            // dp[i] = max(nums[i], nums[i] + dp[i-1])
            dp1 = Math.max(nums[i], nums[i] + dp0);
            dp0 = dp1;
            // 顺便计算最大的结果
            res = Math.max(res, dp1);
        }
        return res;
    }

    /**
     * 53. 最大子数组和
     * https://leetcode.cn/problems/maximum-subarray/
     * 方法一：滑动窗口
     * 思路：窗口内的元素和>=0扩大窗口，元素之和<0缩小窗口，在每次移动窗口时，更新答案。
     * nums 中全是负数的时候，此时算法是可以得到正确答案的;nums 中有正有负，这种情况下元素和最大的那个子数组一定是以正数开头的
     * （以负数开头的话，把这个负数去掉，就可以得到和更大的子数组了，与假设相矛盾）。那么此时我们需要穷举所有以正数开头的子数组，
     * 计算他们的元素和，找到元素和最大的那个子数组。
     *
     * @param nums
     * @return
     */
    // O(n)/O(1)
    public int maxSubArray(int[] nums) {
        int left = 0, right = 0;
        int windowValue = 0, maxValue = Integer.MIN_VALUE;
        while (right < nums.length) {
            // 扩大窗口并更新窗口内的元素和
            windowValue += nums[right];
            right++;
            // 更新答案
            maxValue = windowValue > maxValue ? windowValue : maxValue;
            // 判断窗口是否要收缩 注意这里是while
            while (windowValue < 0) {
                windowValue -= nums[left];
                left++;
            }
        }
        return maxValue;
    }

    /**
     * 300. 最长递增子序列
     * https://leetcode.cn/problems/longest-increasing-subsequence/
     * 方法：耐心排序+二分查找法
     * 思路：将给定的数组中的数字按照指定的规则进行排列，规则：只能把点数小的牌压到点数比它大的牌上；
     * 如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去；如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。
     * 堆顶元素都是按照从小到大的顺序排列的，所以可以使用二分查找法来搜索当前牌应放置的位置。
     * 最终结果：取堆的数量。
     *
     * @param nums
     * @return
     */
    // O(nlogn)/O(n)
    public int lengthOfLIS2(int[] nums) {
        int[] top = new int[nums.length];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // 要处理的扑克牌
            int poker = nums[i];

            /***** 搜索左侧边界的二分查找 *****/
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] < poker) {
                    left = mid + 1;
                } else if (top[mid] > poker) {
                    // 此处需要注意没有-1
                    right = mid;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 没找到合适的牌堆，新建一堆
            if (left == piles) {
                piles++;
            }
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        return piles;
    }

    /**
     * 300. 最长递增子序列
     * https://leetcode.cn/problems/longest-increasing-subsequence/
     * 方法：动态规划
     * 思路：明确数组dp存放的是，nums数组中每个元素结尾的数组中最长递增子序列的长度，也就是题目求什么我们这里就存什么。
     * 寻找当前元素的最长子序列的值只需要在这个元素之前的元素中，找到比这个元素值小的最大元素，这个最大元素的对应的最长子序列的值+1就是结果，
     * 将这个值存入到dp数字中。最后再遍历这个备忘录数组，将最大值求出就是最终的结果。
     *
     * @param nums
     * @return
     */
    // O(n^2)/O(n)
    public int lengthOfLIS(int[] nums) {
        // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[nums.length + 1];
        // base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 寻找 nums[0..j-1] 中比 nums[i] 小的元素
                if (nums[i] > nums[j]) {
                    // 把 nums[i] 接在后面，即可形成长度为 dp[j] + 1，且以 nums[i] 为结尾的递增子序列
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 剑指 Offer II 103. 最少的硬币数目
     * https://leetcode.cn/problems/gaM7Ch/
     * 方法：动态规划【备忘录+迭代】
     * 思路：自底向上，初始化dp数组，里面的值代表的是0-amount金额对应的最小置换硬币数。
     *
     * @param coins
     * @param amount
     * @return
     */
    // O(kn)/O(n)
    public int coinChange3(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                int diff = i - coin;
                if (diff < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], dp[diff] + 1);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

    /**
     * 322. 零钱兑换
     * https://leetcode.cn/problems/coin-change/
     * 方法：动态规划【迭代+备忘录】
     * 思路：自底向上，dp数组中表示值为0-amount的金额，其索引值对应值为最小置换硬币数量。每输入一个amount，会根据之前计算出来的子问题结果，求出换硬币的最小数。
     * 最终求出amount索引对应的置换硬币数。
     *
     * @param coins
     * @param amount
     * @return
     */
    // O(kn)/O(n)
    // 子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。k是面额数
    public int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 数组大小为 amount + 1，初始值也为 amount + 1
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                int diff = i - coin;
                // 子问题无解，跳过
                if (diff < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], dp[diff] + 1);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }


    /**
     * 322. 零钱兑换
     * https://leetcode.cn/problems/coin-change/
     * 方法：动态规划【递归+备忘录】
     * 思路：自顶向下，函数中的参数是状态转移中会变化的量，也就是我们说的状态，函数的返回值就是我们要计算的量。通过备忘录减少子问题的数目，
     * 降低时间复杂度。
     *
     * @param coins
     * @param amount
     * @return
     */
    int[] memo;

    // O(kn)/O(n)
    // 子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。k是面额数
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
        Arrays.fill(memo, -666);
        return dp(coins, amount);
    }

    private int dp(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        // 没有找到合适纸币
        if (amount < 0) {
            return -1;
        }
        // 查备忘录，防止重复计算
        if (memo[amount] != -666) {
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) {
                continue;
            }
            // 在子问题中选择最优解，然后加一
            res = Math.min(res, subProblem + 1);
        }
        // 把计算结果存入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }


    /**
     * 28. 找出字符串中第一个匹配项的下标
     * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
     * 方法：Rabin-Karp【滑动哈希技巧+取余求哈希值】
     * 思路：先将目标字符串needle转化为hash数字，在窗口滑动的过程中，计算窗口中的字符串转化成的数字【窗口的hash值】，字符左->右对应数字高位->低位，当数字的位数
     * 达到L时，缩小窗口。【注意整个计算hash值的过程都需要%】
     * 只要遇到和needle的hash值相同的数字，然后判断needle和s.substring(left,right)相同，就直接返回left。注意类型long
     *
     * @param haystack
     * @param needle
     * @return
     */
    // O(N+L)/O(1)
    public int strStr(String haystack, String needle) {
        // 位数
        int L = needle.length();
        // 进制（只考虑 ASCII 编码）
        int R = 256;
        // R^(L - 1) 的结果
        long RL = 1;
        int n = L - 1;
        // 取一个比较大的素数作为求模的除数
        long Q = 1658598167;
        for (int i = 0; i < n; i++) {
            // 计算过程中不断求模，避免溢出
            RL = (RL * R) % Q;
        }

        // 计算模式串的哈希值，时间 O(L)
        long targetHash = 0;
        for (int i = 0; i < L; i++) {
            targetHash = (targetHash * R + needle.charAt(i)) % R;
        }
        // 滑动窗口中子字符串的哈希值
        long windowHash = 0;
        // 滑动窗口代码框架，时间 O(N)
        int left = 0, right = 0;
        while (right < haystack.length()) {
            // 扩大窗口，移入字符
            windowHash = (windowHash * R + haystack.charAt(right)) % R;
            right++;
            // 当子串的长度达到要求
            while (right - left == L) {
                // 根据哈希值判断是否匹配模式串
                // 当前窗口中的子串哈希值等于模式串的哈希值
                // 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突
                if (windowHash == targetHash && haystack.substring(left, right).equals(needle)) {
                    return left;
                }
                // 缩小窗口，移出字符
                windowHash = (windowHash - RL * haystack.charAt(left) % Q + Q) % Q;
                // X % Q == (X + Q) % Q 是一个模运算法则
                // 因为 windowHash - (txt[left] * RL) % Q 可能是负数
                // 所以额外再加一个 Q，保证 windowHash 不会是负数
                left++;
            }
        }
        // 没有找到模式串
        return -1;
    }

    /**
     * 187. 重复的DNA序列
     * https://leetcode.cn/problems/repeated-dna-sequences/
     * 方法：滑动哈希技巧
     * 思路：先将s字符串中的字符转化为数字，在窗口滑动的过程中，计算窗口中的字符串转化成的数字【窗口的hash值】，字符左->右对应数字高位->低位，当数字的位数
     * 达到L时，缩小窗口。用一个set集合【校验数字是否出现过，也就是检查子字符串是否出现过】记录出现的重复数字的子字符集，
     * 只要遇到重复的数字就s.substring(left,right)【时间复杂度为O(L)】，否则将数字加入另一个存取数字的set集合
     *
     * @param s
     * @return
     */

    // O(N)/O(N)   一般情况下的平均时间复杂度是 O(N)，极端情况下的时间复杂度会退化成 O(NL)【substring 方法需要 O(L) 的复杂度】
    public List<String> findRepeatedDnaSequences(String s) {
        // 先把字符串转化成四进制的数字数组
        int[] nums = new int[s.length()];
        for (int i = 0; i < nums.length; i++) {
            switch (s.charAt(i)) {
                case 'A':
                    nums[i] = 0;
                    break;
                case 'C':
                    nums[i] = 1;
                    break;
                case 'G':
                    nums[i] = 2;
                    break;
                case 'T':
                    nums[i] = 3;
                    break;
                default:
                    break;
            }
        }
        // 滑动窗口代码框架，时间 O(N)
        int left = 0, right = 0;
        // 进制   数字位数
        int R = 4, L = 10;
        // 存储 R^(L - 1) 的结果【后面几个0 L-1个】
        int RL = (int) Math.pow(R, L - 1);
        // 维护滑动窗口中字符串的哈希值
        int windowHash = 0;
        // 记录重复出现的哈希值
        Set<Integer> seen = new HashSet<>();
        // 记录重复出现的字符串结果
        Set<String> res = new HashSet<>();
        while (right < nums.length) {
            // 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）
            windowHash = windowHash * R + nums[right];
            right++;
            // 当子串的长度达到要求
            while (right - left == L) {
                // 根据哈希值判断是否曾经出现过相同的子串
                if (seen.contains(windowHash)) {
                    // 当前窗口中的子串是重复出现的
                    res.add(s.substring(left, right));
                } else {
                    // 当前窗口中的子串之前没有出现过，记下来
                    seen.add(windowHash);
                }
                // 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）
                windowHash = windowHash - RL * nums[left];
                left++;
            }
        }
        // 转化成题目要求的 List 类型
        return new LinkedList<>(res);
    }


    /**
     * 剑指 Offer II 016. 不含重复字符的最长子字符串
     * https://leetcode.cn/problems/wtcaE1/
     * 方法：滑动窗口
     *
     * @param s
     * @return
     */
    // O(n)/O(C)  n 是字符串的长度。左指针和右指针分别会遍历整个字符串一次；C:表示map中字符集大小
    public int lengthOfLongestSubstring4(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            while (window.get(c).intValue() > 1) {// 遇到重复元素就缩小窗口
                char d = s.charAt(left);
                if (window.containsKey(d)) {
                    window.put(d, window.get(d).intValue() - 1);
                }
                left++;

            }
            res = Math.max(res, right - left);
        }
        return res;
    }

    /**
     * 剑指 Offer II 015. 字符串中的所有变位词
     * https://leetcode.cn/problems/VabMRr/
     * 方法：滑动窗口
     *
     * @param s
     * @param p
     * @return
     */
    // O(C*|s-p|+|p|)/O(C)   需要判断 s-p+1 个滑动窗口中每种字母的数量是否与字符串p中每种字母的数量相同，每次判断需要O(C)
    // C:表示map中字符集大小，用于存储字符串p和滑动窗口中每种字母的数量
    public List<Integer> findAnagrams2(String s, String p) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (need.get(c).equals(window.get(c))) {
                    valid++;
                }
            }
            while (right - left >= p.length()) {
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (need.get(d).equals(window.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d).intValue() - 1);
                }
            }
        }
        return res;
    }


    /**
     * 剑指 Offer II 014. 字符串中的变位词
     * https://leetcode.cn/problems/MPnaiL/description/
     * 方法：滑动窗口
     * 思路：此题与字符串的排列相同，首先将子串存入一个map中变量名为need，同时计数字符个数，利用左右指针，向前滑动，将划入窗口的字符存储在一个map中变量名为window。
     * 使用一个valid变量计数窗口中出现符合目标串字符的个数，在缩小窗口的时候，此时判断valid和need的key个数是否一样，一样的话就找到了。
     * 缩短窗口的条件：窗口中的字符个数>=s1字符个数
     *
     * @param s1
     * @param s2
     * @return
     */

    public boolean checkInclusion2(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : s1.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0).intValue() + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        while (right < s2.length()) {
            char c = s2.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            while (right - left >= s1.length()) {
                if (valid == need.size()) {
                    return true;
                }
                char d = s2.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d).intValue() - 1);
                }
            }
        }
        return false;
    }

    /**
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     * https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/
     * 方法：滑动窗口
     * 思路：左右指针在移动的过程中，窗口中的元素存入一个map中，缩小窗口的条件是划入窗口的元素在map已经存在
     *
     * @param s
     * @return
     */
    // O(C*|s|)/O(C)   C:表示map中字符集大小
    public int lengthOfLongestSubstring3(String s) {
        int left = 0, right = 0, res = 0;
        Map<Character, Integer> needMap = new HashMap<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            needMap.put(c, needMap.getOrDefault(c, 0) + 1);
            // 划入窗口的元素出现重复元素，缩小窗口
            while (needMap.get(c) > 1) {
                char d = s.charAt(left);
                needMap.put(d, needMap.get(d) - 1);
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }

    /**
     * 1438. 绝对差不超过限制的最长连续子数组
     * https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/?show=1
     * 方法：滑动窗口
     * 思路：因为要计算存在的子数组中任意两个元素的绝对值差<=limit，换句话说就是求出子数组中最大值和最小值的差值<=limit，这样子数组中的其它值之差也会<=limit。
     * 可以使用两个单调的队列，一个单调递增的队列queMin维护最小值，一个单调递减的队列queMax维护最大值，只需要计算两个队列的队首差值便可知道，当前窗口是否满足条件。
     * 利用左右指针，在左右指针向前话动的过程中，窗口右端值需要和queMax、queMin的队尾元素比较，更新队列中的值。
     * 缩小窗口的条件是，队首差值>limit，然后每次窗口移动都需要比较此时窗口和之前窗口的大小。
     *
     * @param nums
     * @param limit
     * @return
     */
    // O(n)/O(n) 我们最多遍历该数组两次，两个单调队列入队出队次数也均为 O(n)/最坏情况下单调队列将和原数组等大
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> queMin = new LinkedList<>();
        Deque<Integer> queMax = new LinkedList<>();
        int left = 0, right = 0;
        int res = 0;
        // 右指针针对的是队尾元素，左指针针对的是队首元素
        while (right < nums.length) {
            // 比较队列队尾元素与当前数组元素的大小，注意这里是while
            // 如果最大队列的队尾元素比当前值还小，即最大队列的最小值比当前值还小，那么弹出队尾元素
            while (!queMax.isEmpty() && queMax.peekLast() < nums[right]) {
                queMax.pollLast();
            }
            // 如果最小队列的队尾元素比当前值还大，即最小队列的最大值比当前值还大，那么弹出队尾元素
            while (!queMin.isEmpty() && queMin.peekLast() > nums[right]) {
                queMin.pollLast();
            }
            // 更新队列
            queMax.offerLast(nums[right]);
            queMin.offerLast(nums[right]);
            // 缩小窗口
            while (!queMax.isEmpty() && !queMin.isEmpty() && queMax.peekFirst() - queMin.peekFirst() > limit) {
                // 排查重复元素
                if (nums[left] == queMax.peekFirst()) {
                    queMax.pollFirst();
                }
                if (nums[left] == queMin.peekFirst()) {
                    queMin.pollFirst();
                }
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }

    /**
     * 1004. 最大连续1的个数 III
     * https://leetcode.cn/problems/max-consecutive-ones-iii/description/?show=1
     * 方法：前缀和+滑动窗口
     * 思路：理解题意，最大连续1的个数，包含k个0反转为1，如果我们将原始数组中的0转为1，1转为0，那么可以转为求和为k的子数组两个首位元素的最长距离，
     * 这里应用到的滑动窗口，其实就是求滑动窗口中<=k个1之和的最长宽度，这里求和最大为k利用到了前缀和，也就是右指针的前面所有元素之和-左指针的前面所有元素之和=窗口中
     * 1的所有和
     */
    // O(n)/O(1)   其中n是数组A的长度。我们至多只需要遍历该数组两次（左右指针各一次）
    public int longestOnes(int[] nums, int k) {
        int left = 0, right = 0;
        int lsum = 0, rsum = 0;
        int res = 0;
        while (right < nums.length) {
            // 这里0转1，1转0操作注意是用1减当前元素
            rsum += 1 - nums[right];
            while (k < rsum - lsum) {
                // 窗口元素之和超过k，就要缩小窗口
                lsum += 1 - nums[left];
                left++;
            }
            res = Math.max(res, right - left + 1);
            // 这里注意，right++写在计算窗口长度之后，因为res计算的是当前两个前缀和左右指针的距离
            right++;
        }
        return res;
    }

    /**
     * 3. 无重复字符的最长子串
     * https://leetcode.cn/problems/longest-substring-without-repeating-characters/
     * 方法：滑动窗口
     * 思路：滑动窗口使用左右指针组成，窗口通过右指针不断前进，当遇到重复字符的时候，此时需要缩小窗口，左指针右移，更新窗口中的值
     *
     * @param s
     * @return
     */
    // O(C*|s|)/O(C)   C:表示map中字符集大小
    public int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> window = new HashMap<>();
        // res:记录结果
        int left = 0, right = 0, res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 遇到重复元素，缩小窗口
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                window.put(d, window.get(d) - 1);
            }
            // 在这里更新答案
            res = Math.max(res, right - left);
        }
        return res;
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
     * 方法：滑动窗口
     * 思路：滑动窗口使用左右指针组成，窗口通过右指针不断前进，划入窗口的的值是目标子串中的字符，当窗口中的字符与目标中的子串字符字数相同的时候，此时将窗口中字符
     * 所在索引位置放入结果集中，否则需要缩小窗口，直到右指针到达s的末端
     *
     * @param s
     * @param p
     * @return
     */
    // O(C*|s|+|p|)/O(C)   C:表示map中字符集大小
    public List<Integer> findAnagrams(String s, String p) {
        // 记录结果
        List<Integer> res = new ArrayList<>();
        int left = 0, right = 0;
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int valid = 0;
        while (right < s.length()) {
            // 进行窗口内数据的一系列更新
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 易错点，主要这里需要need在前面
                if (need.get(c).equals(window.get(c))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while (right - left >= p.length()) {// 易错点
                // 当窗口符合条件时，把起始索引加入 res
                if (need.size() == valid) {
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (need.get(d).equals(window.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d).intValue() - 1);
                }
            }
        }
        return res;
    }

    /**
     * 567. 字符串的排列
     * https://leetcode.cn/problems/permutation-in-string/
     * 方法：滑动窗口
     * 思路：滑动窗口是使用左右双指针组成，窗口通过右指针在不断向右前行，划入窗口的值是目标子串中的字符，当窗口中的字符与目标中的子串字符相符合时候，返回true
     * 否则，需要缩小窗口，左指针向右前行，直到右指针到达s的末端
     *
     * @param s1
     * @param s2
     * @return
     */
    // O(C*|s|+|t|)/O(C)   C:表示map中字符集大小  t:s1长度，s:s2长度
    public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = 0;
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : s1.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int valid = 0;
        while (right < s2.length()) {
            char c = s2.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 注意：这里不要使用==，超过-128到127之间的数，就不是在缓存中直接取数值了，也是转换为对象地址的比较
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (right - left >= s1.length()) {
                if (valid == need.size()) {
                    return true;
                }
                char d = s2.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d).intValue() - 1);
                }

            }
        }
        //  未找到符合条件的子串
        return false;
    }

    /**
     * 1329. 将矩阵按对角线排序
     * https://leetcode.cn/problems/sort-the-matrix-diagonally/description/?show=1
     * 方法：双指针
     * 思路：两个点：一个是找到对角的线的值，假设对角线的起始坐标是[i,j]，那么沿着对角线的值依次为[i++,j++]；另一个是排序。
     * 使用冒泡排序，这里注意想到一共排序多少次，即Math.min(m,n) - 1。
     *
     * @param mat
     * @return
     */

    // O(min(m,n) *m*n)/O(1)
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        // 冒泡排序 排序次数：Math.min(m,n) - 1
        int sortSize = Math.min(m, n) - 1;
        for (int k = 0; k < sortSize; k++) {
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    int next = mat[i + 1][j + 1];
                    if (mat[i][j] > next) {
                        int temp = next;
                        mat[i + 1][j + 1] = mat[i][j];
                        mat[i][j] = temp;
                    }
                }
            }
        }
        return mat;
    }

    /**
     * 59. 螺旋矩阵 II
     * https://leetcode.cn/problems/spiral-matrix-ii/
     * 方法：圈定边界遍历数组
     * 思路：按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界，给遍历到的当前位置复制+1后的元素
     */
    // O(m*n)/O(1)
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int upperBound = 0, downBound = n - 1;
        int leftBound = 0, rightBound = n - 1;
        // 需要填入矩阵的数字
        int num = 1;

        while (num <= n * n) {
            if (upperBound <= downBound) {
                // 在顶部从左向右遍历
                for (int j = leftBound; j <= rightBound; j++) {
                    matrix[upperBound][j] = num++;
                }
                upperBound++;
            }
            if (leftBound <= rightBound) {
                // 在右侧从上向右下历
                for (int i = upperBound; i <= downBound; i++) {
                    matrix[i][rightBound] = num++;
                }
                rightBound--;
            }
            if (upperBound <= downBound) {
                // 在底部从右向左遍历
                for (int j = rightBound; j >= leftBound; j--) {
                    matrix[downBound][j] = num++;
                }
                downBound--;
            }
            if (leftBound <= rightBound) {
                // 在左侧从下向上遍历
                for (int i = downBound; i >= upperBound; i--) {
                    matrix[i][leftBound] = num++;
                }
                leftBound++;
            }
        }
        return matrix;
    }

    /**
     * 54. 螺旋矩阵
     * https://leetcode.cn/problems/spiral-matrix/
     * 方法：圈定边界遍历数组
     * 思路：按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界
     *
     * @param matrix
     * @return
     */

    // O(m*n)/O(1)
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList<>();
        }
        int m = matrix.length, n = matrix[0].length;
        int upperBound = 0, downBound = m - 1;
        int leftBound = 0, rightBound = n - 1;
        List<Integer> res = new ArrayList<>();
        // res.size() == m * n 则遍历完整个数组
        while (res.size() < m * n) {
            if (upperBound <= downBound) {
                // 在顶部从左向右遍历
                for (int j = leftBound; j <= rightBound; j++) {
                    res.add(matrix[upperBound][j]);
                }
                // 上边界下移
                upperBound++;
            }
            if (leftBound <= rightBound) {
                // 在右侧从上向下遍历
                for (int i = upperBound; i <= downBound; i++) {
                    res.add(matrix[i][rightBound]);
                }
                // 右边界左移
                rightBound--;
            }
            if (upperBound <= downBound) {
                // 在下部从右向左遍历
                for (int j = rightBound; j >= leftBound; j--) {
                    res.add(matrix[downBound][j]);
                }
                // 下边界上移
                downBound--;
            }
            if (leftBound <= rightBound) {
                // 在左侧从下向上遍历
                for (int i = downBound; i >= upperBound; i--) {
                    res.add(matrix[i][leftBound]);
                }
                // 左边界右移
                leftBound++;
            }
        }
        return res;
    }

    /**
     * 扩展：旋转图像
     * https://leetcode.cn/problems/rotate-image/
     * 方法：二维数组镜像对称+双指针
     * 思路：首先对二维数组进行行和列的镜像按照右对角线对称转换【注意在寻找对角线的右下方值时候的坐标，需要使用到n-1去计算】，然后对每行数组使用双指针进行反转
     *
     * @param matrix
     */
    // O(n^2)/O(1)

    // 将二维矩阵原地逆时针旋转 90 度
    public void rotate2(int[][] matrix) {
        int n = matrix.length;
        // 沿左下到右上的对角线镜像对称二维矩阵
        for (int i = 0; i < n; i++) {
            // 取上半块
            for (int j = 0; j < n - i; j++) {
                int temp = matrix[i][j];
                // 注意取值时候的坐标
                int row = n - 1 - j;
                int column = n - 1 - i;
                matrix[i][j] = matrix[row][column];
                matrix[row][column] = temp;
            }
        }

        // 反转每行的元素
        for (int[] row : matrix) {
            int left = 0, right = row.length - 1;
            while (left < right) {
                int temp = row[left];
                row[left] = row[right];
                row[right] = temp;
                left++;
                right--;
            }
        }
    }

    /**
     * 48. 旋转图像
     * https://leetcode.cn/problems/rotate-image/
     * 方法：二维数组镜像对称+双指针
     * 思路：首先对二维数组进行行和列的镜像按照左对角线对称转换，然后对每行数组使用双指针进行反转
     *
     * @param matrix
     */
    // O(n^2)/O(1)

    // 将二维矩阵原地顺时针旋转 90 度
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 先沿对角线镜像对称二维矩阵
        for (int i = 0; i < n; i++) {// 行
            // 取上半块
            for (int j = i; j < n; j++) {// 列
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 反转二维矩阵的每一行
        for (int[] row : matrix) {
            int left = 0, right = row.length - 1;
            while (left < right) {
                int temp = row[left];
                row[left] = row[right];
                row[right] = temp;
                left++;
                right--;
            }
        }
    }


    /**
     * 151. 反转字符串中的单词
     * https://leetcode.cn/problems/reverse-words-in-a-string/description/
     * 方法：双指针
     * 思路：反向循环字符串，首先先跳过空格，然后找到单词的首和尾的索引位置，最后将单词存入到StringBuilder的变量中
     *
     * @param s
     * @return
     */
    // O(n)/O(1)
    public static String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int start, end;// 每个单词的开始和结束索引（左闭右闭）
        StringBuilder sbr = new StringBuilder();
        // 注意这里是>=
        for (int i = s.length() - 1; i >= 0; i--) {
            // 跳过单词后面的空格
            if (s.charAt(i) == ' ') {
                continue;
            }
            // 找到单词的结束索引
            end = i;
            // 注意这里是>=0
            while (i > 0 && s.charAt(i) != ' ') {
                i--;
            }
            // 找到单词的开始索引
            start = i + 1;
            // 将每个单词字符赋值到StringBuilder
            // 注意这里是<=
            for (int j = start; j < end; j++) {
                sbr.append(s.charAt(j));
            }
            // 加上单词间的空格
            sbr.append(' ');
        }
        if (sbr.length() > 0) {
            // 删掉最后一个多余的空格
            sbr.deleteCharAt(sbr.length() - 1);
        }
        return sbr.toString();
    }

    /**
     * 1094. 拼车
     * https://leetcode.cn/problems/car-pooling/
     * 方法：差分数组
     * 思路：这题翻译过来就是，车每趟行驶过程中，车上的人都不能超过限定人数也就是容量值。根据题目要求，1 <= trips.length <= 1000，也就是最多有1001趟行驶。
     * 此时初始化1001大小的数组，值都是0，也就是最开始车上是没人的，保证每趟行驶的中，两个站点之间车上的旅客不能超载。
     *
     * @param trips
     * @param capacity
     * @return
     */
    // O(n+m)，其中 n 为数组长度，m 为趟数。
    // O(1)
    public boolean carPooling(int[][] trips, int capacity) {
        // 最多有 1001 个车站
        int[] nums = new int[1001];
        // 构造差分解法
        Difference difference = new Difference(nums);

        for (int[] trip : trips) {
            // 乘客数量
            int numPassengers = trip[0];
            // 第 trip[1] 站乘客上车
            int from = trip[1];
            // 第 trip[2] 站乘客已经下车，即乘客在车上的区间是 [trip[1], trip[2] - 1]
            int to = trip[2] - 1;
            // 进行区间操作
            difference.increment(from, to, numPassengers);
        }
        int[] res = difference.result();
        // 客车自始至终都不应该超载
        for (int i = 0; i < res.length; i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }


    /**
     * 1109. 航班预订统计
     * https://leetcode.cn/problems/corporate-flight-bookings/
     * 方法：差分数组
     * 思路：看到这种二元数组，同时其中列元素是三元数组的，先想想可不可以使用三元数组。首先将题目转换为差分数组可以解题的形式。每个预订记录是其实翻译过来就是
     * 每个航班的座位都是没被预订的，也就是nums[n]的每个元素初始都是0， i~j编号区间的数值+k。
     *
     * @param bookings
     * @param n
     * @return
     */
    // O(n+m)，其中 n 为要求的数组长度，m 为预定记录的数量。
    // O(1)
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums = new int[n];
        Difference difference = new Difference(nums);
        for (int[] booking : bookings) {
            // 注意这里的值，题目给的是第几号航班，是从1开始的，所以我们需要转换成数组下标的形式
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int k = booking[2];
            difference.increment(i, j, k);
        }
        return difference.result();
    }

    private class Difference {
        private int[] diff;

        // O(1)
        public Difference(int[] nums) {
            if (nums.length == 0) {
                return;
            }
            // 初始化查分数组
            diff = new int[nums.length];
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        // 给指定区间+val
        public void increment(int i, int j, int val) {
            diff[i] += val;
            int nextRight = j + 1;
            if (nextRight < diff.length) {
                diff[nextRight] -= val;
            }
        }

        // 获取查分数组转换后的结果
        public int[] result() {
            if (diff == null) {
                return null;
            }
            int[] res = new int[diff.length];
            res[0] = diff[0];
            for (int i = 1; i < diff.length; i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
    }

    /**
     * 5. 最长回文子串
     * https://leetcode.cn/problems/longest-palindromic-substring/description/
     * 方法：双指针：左右指针【从中心想两端扩散】
     * 思路：回文串的的长度可能是奇数也可能是偶数。如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。
     * 从中心向两端扩散的双指针。
     *
     * @param s
     * @return
     */
    // O(n^2)/O(1)
    public String longestPalindrome3(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    // 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
    private String palindrome(String s, int left, int right) {
        // 防止索引越界
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 双指针，向两边展开
            left--;
            right++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(left + 1, right);
    }

    /**
     * 46. 全排列
     * https://leetcode.cn/problems/permutations/
     * 方法：回溯法+决策树
     * 思路：在每个节点上做决策。每个节点前后的树枝，分别代表了决策前(已做出的选择)和决策后(未作出的选择)，当走到树的底层叶子节点，
     * 即当未做出的选择没有的时候，表示找到一个全排序。
     * 即路径：记录你已经做过的选择；选择列表：表示你当前可以做出的选择；
     * 结束条件：就是遍历到树的底层叶子节点，这里也就是选择列表为空的时候。
     *
     * @param nums
     * @return
     */
    // O(n×n!)/O(n)
    // 时间复杂度：backtrack 的调用次数是 O(n!)的，需要将当前答案使用O(n)的时间复制到答案数组中，相乘得时间复杂度为 O(n×n!)
    // 空间复杂度：递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度
    List<List<Integer>> res = new LinkedList<>();

    // 函数，输入一组不重复的数字，返回它们的全排列
    public List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        List<Integer> track = new LinkedList<>();
        // 「路径」中的元素会被标记为 true，避免重复使用
        boolean[] used = new boolean[nums.length];
        backTrack(nums, track, used);
        return res;
    }

    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
    // 结束条件：nums 中的元素全都在 track 中出现
    private void backTrack(int[] nums, List<Integer> track, boolean[] used) {
        // // 触发结束条件，寻找到一个全排列
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (used[i]) {
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.add(nums[i]);
            used[i] = true;
            // 进入下一层决策树
            backTrack(nums, track, used);
            // 取消选择
            track.remove(track.size() - 1);
            used[i] = false;
        }
    }

    /**
     * 215. 数组中的第K个最大元素
     * 方法：快速选择排序
     * 思路：确定倒序k位置在正序排序中的索引位置，为避免生成长链表的引起时间复杂度过大的情况，首先先对数组进行乱序。
     * partition 函数会将 nums[p] 排到正确的位置，使得 nums[lo..p-1] < nums[p] < nums[p+1..hi]。判断k在p的左侧还是右侧，利用二分查找思想
     * 找到k=p的位置就是寻找的结果。
     *
     * @param nums
     * @param k
     * @return
     */
    // O(n)/O(logn):递归使用栈空间的空间代价的期望为O(logn)
    public int findKthLargest2(int[] nums, int k) {
        // 首先随机打乱数组
        shuffle2(nums);
        int lo = 0, hi = nums.length - 1;
        // 转化成「排名第 k 的元素」
        k = nums.length - k;
        while (lo <= hi) {
            // 在 nums[lo..hi] 中选一个分界点
            int p = partition2(nums, lo, hi);
            if (p < k) {
                // 第 k 大的元素在 nums[p+1..hi] 中
                lo = p + 1;
            } else if (p > k) {
                // 第 k 大的元素在 nums[lo..p-1] 中
                hi = p - 1;
            } else {
                // 找到第 k 大元素
                return nums[p];
            }
        }
        return -1;
    }

    private int partition2(int[] nums, int low, int high) {
        int pivot = nums[low];
        int i = low + 1, j = high;
        // nums[j]<=pivot<nums[i]
        while (i <= j) {
            while (i < high && nums[i] <= pivot) {
                i++;
            }
            while (j > low && nums[j] > pivot) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, low, j);
        return j;
    }

    private void shuffle2(int[] nums) {
        int n = nums.length;
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            int r = i + random.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    /**
     * 215. 数组中的第K个最大元素
     * 方法：二叉堆
     * 思路：二叉堆默认对元素从小到大排列，将k个元素之外的元素弹出后则堆头部第一个元素就是第K大的数
     *
     * @param nums
     * @param k
     * @return
     */
    // O(nlogk)/O(k)
    // 复杂度分析:二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过 k，所以插入和删除元素的复杂度是 O(logk)，
    // 再套一层 for 循环，假设数组元素总数为 N，总的时间复杂度就是 O(Nlogk)
    // 空间复杂度很显然就是二叉堆的大小，为 O(k)
    public int findKthLargest(int[] nums, int k) {
        // 小顶堆，堆顶是最小元素
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            // 每个元素都要过一遍二叉堆
            queue.offer(nums[i]);
            // 堆中元素多于 k 个时，删除堆顶元素
            if (queue.size() > k) {
                queue.poll();
            }
        }
        // queue中剩下的是 nums 中 k 个最大元素，堆顶是最小的那个，即第 k 个最大元素
        return queue.peek();
    }

    /**
     * https://leetcode.cn/problems/sort-an-array/
     * 912. 排序数组
     * 方法：快速排序
     * 思路：先将一个元素排好序，然后再将剩下的元素排好序。
     * 找到一个分隔值，然后排序左右子数组，这个过程类似构建二叉树的先序遍历，此时为了防止出现单链表的情况（提升性能），我们先对整个数组
     * 进行一个顺序的打乱。然后找这个切点的过程是双指针，先将low位置的元素定为pivot，然后寻找切点位置p，左指针i=low+1，右指针j=high，左右
     * 开工，直到两者相遇，也就找到了p=j，将j与low位置的元素交换，也就是将pivot放在指定位置，保证其左侧元素都比它小，右侧元素都比它大。
     *
     * @param nums
     * @return
     */
    // O(NlogN)/递归堆栈的深度O(logN)
    public int[] sortArray2(int[] nums) {
        // 为了避免出现耗时的极端情况，先随机打乱
        shuffle(nums);
        // 排序整个数组（原地修改）
        sortQuick(nums, 0, nums.length - 1);
        return nums;
    }

    private void sortQuick(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        int p = partition(nums, low, high);
        sortQuick(nums, low, p - 1);
        sortQuick(nums, p + 1, high);
    }

    // 对 nums[lo..hi] 进行切分，寻找分隔点的位置
    private int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        // 关于区间的边界控制需格外小心，稍有不慎就会出错
        // 我这里把 i, j 定义为开区间，同时定义：
        // [lo, i) <= pivot；(j, hi] > pivot
        // 之后都要正确维护这个边界区间的定义
        int i = low + 1, j = high;
        while (i <= j) {
            // 此 while 结束时恰好 nums[i] > pivot
            while (i < high && nums[i] <= pivot) {
                i++;
            }
            // 此 while 结束时恰好 nums[j] <= pivot
            while (j > low && nums[j] > pivot) {
                j--;
            }
            // 指针相遇，此时 [lo, i) <= pivot && (j, hi] > pivot
            if (i >= j) {
                break;
            }
            // 指针未相遇，但是nums[j]<=pivot<nums[i]
            swap(nums, i, j);
        }
        // 将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        swap(nums, low, j);
        return j;
    }

    // 洗牌算法，将输入的数组随机打乱
    private void shuffle(int[] nums) {
        Random random = new Random();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + random.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    // 交换数组的两个元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * https://leetcode.cn/problems/sort-an-array/
     * 912. 排序数组
     * 方法：归并排序
     * 思路：分解法+后序遍历，将数组左半边作为左子树，右半边作为右子树，先做子树排序，在右子树排序，最后合并。
     *
     * @param nums
     * @return
     */
    //O(nlogn)/O(n)
    int[] temp2;

    public int[] sortArray(int[] nums) {
        temp2 = new int[nums.length];
        sort2(nums, 0, nums.length - 1);
        return nums;
    }

    private void sort2(int[] nums, int low, int high) {
        if (low == high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort2(nums, low, mid);
        sort2(nums, mid + 1, high);
        merge2(nums, low, mid, high);
    }

    private void merge2(int[] nums, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            temp2[i] = nums[i];
        }
        // 注意j
        int i = low, j = mid + 1;
        for (int p = low; p <= high; p++) {
            if (i == mid + 1) {
                nums[p] = temp2[j++];
                //注意此条件
            } else if (j == high + 1) {
                nums[p] = temp2[i++];
            } else if (temp2[i] > temp2[j]) {
                nums[p] = temp2[j++];
            } else {
                nums[p] = temp2[i++];
            }
        }
    }

    /**
     * 归并排序模板
     *
     * @param nums
     */
    // n(logn)/n
    // 用于辅助合并有序数组
    int[] temp;

    public void sort(int[] nums) {
        // 先给辅助数组开辟内存空间
        temp = new int[nums.length];
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }

    // 定义：将子数组 nums[lo..hi] 进行排序
    private void sort(int[] nums, int low, int high) {
        if (low == high) {
            // 单个元素不用排序
            return;
        }
        // 这样写是为了防止溢出【low+high时可能溢出的】，效果等同于 (hi + lo) / 2
        int mid = low + (high - low) / 2;
        // 先对左半部分数组 nums[lo..mid] 排序
        sort(nums, low, mid);
        // 再对右半部分数组 nums[mid+1..hi] 排序
        sort(nums, mid + 1, high);
        // 将两部分有序数组合并成一个有序数组
        merge(nums, low, mid, high);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组。时间复杂度O(n)
    private void merge(int[] nums, int low, int mid, int high) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        for (int i = low; i < high; i++) {
            temp[i] = nums[i];
        }
        // 数组双指针技巧，合并两个有序数组，注意j
        int i = low, j = mid + 1;
        for (int p = low; p <= high; p++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                nums[p] = temp[j++];
                //注意此条件
            } else if (j == high + 1) {
                // 右半边数组已全部被合并
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }

    /**
     * 238. 除自身以外数组的乘积
     * https://leetcode.cn/problems/product-of-array-except-self/?show=1
     * 方法：前缀和系列-前缀积
     * 思路：构造一个 prefix 数组记录「前缀积」，再用一个 suffix 记录「后缀积」，根据前缀和后缀积就能计算除了当前元素之外其他元素的积。
     *
     * @param nums
     * @return
     */
    // O(n)/O(n)
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        // 计算从左到右的前缀积，prefix[i] 是 nums[0..i] 的元素积
        int[] prefix = new int[len];
        // 初始化前缀积的首元素
        prefix[0] = nums[0];
        for (int i = 1; i < len; i++) {
            prefix[i] = prefix[i - 1] * nums[i];
        }
        // 计算从右到左的前缀积，suffix[i] 是 nums[i..n-1] 的元素积
        int[] suffix = new int[len];
        // 初始化后缀积的首元素
        suffix[len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i];
        }
        // 结果数组
        int[] res = new int[len];
        // 处理边界问题
        res[0] = suffix[1];
        res[len - 1] = prefix[len - 2];
        for (int i = 1; i < nums.length - 1; i++) {
            // 除了 nums[i] 自己的元素积就是 nums[i] 左侧和右侧所有元素之积
            res[i] = prefix[i - 1] * suffix[i + 1];
        }
        return res;
    }

    /**
     * 1352. 最后 K 个数的乘积
     * https://leetcode.cn/problems/product-of-the-last-k-numbers/?show=1
     * 方法：前缀和系列-前缀积
     * 思路：和前缀和思想类似，后k个元素的积=preProduct[n-1]/preProduct[n-k-1](n为前缀积集合的长度)，添加过程需要
     * 考虑元素为0的情况，若遇到0，那么之前的前缀积作废，直接清除；在取结果的过程中会判断，如果k比n-1大(n:前缀积数组长度)，直接返回0。
     * n-1原因：前缀积第一个元素是人为加的1，减1之后会是数字列表的元素数量；不到k个元素，说明数字列表最后的k个元素有0
     */
    // O(1)/O(n)
    class ProductOfNumbers {
        // 定义一个前缀积集合
        // preProduct[i] / preProduct[j] 就是 [i, j] 之间的元素积
        List<Integer> preProduct = new ArrayList<>();

        public ProductOfNumbers() {
            // 初始化放一个 1，便于计算后续添加元素的乘积
            preProduct.add(1);
        }

        public void add(int num) {
            if (num == 0) {
                // 如果添加的元素是 0，则前面的元素积都废了
                preProduct.clear();
                preProduct.add(1);
                return;
            }
            int len = preProduct.size();
            // 前缀积数组中每个元素
            preProduct.add(preProduct.get(len - 1) * num);
        }

        public int getProduct(int k) {
            int len = preProduct.size();
            if (k > len - 1) {
                // 不足 k 个元素，是因为最后 k 个元素存在 0
                return 0;
            }
            // 计算最后 k 个元素积
            return preProduct.get(len - 1) / preProduct.get(len - k - 1);
        }
    }

    /**
     * 560. 和为 K 的子数组
     * https://leetcode-cn.com/problems/subarray-sum-equals-k/?show=1
     * 方法：前缀和
     * 思路：计算数数组的前缀和，preSum[i]-preSum[j]=k从而得出need=preSum[i]-k，将前缀和:前缀和出现的次数保存在hashmap中，
     * 然后在这个map中找到need对应的数量，将每个need出现的数量进行累计便是最终结果。
     * 由于map保存是perSum数组的每个不重复元素，所以我们这里使用一次遍历就可以求出。
     *
     * @param nums
     * @param k
     * @return
     */
    // O(n)/O(n)
    public int subarraySum(int[] nums, int k) {
        // 计算前缀和
        int[] preSum = new int[nums.length + 1];
        // 前缀和到索引的映射，方便快速查找所需的前缀和
        // key:value=前缀和:前缀和出现的次数
        HashMap<Integer, Integer> valToCount = new HashMap<>();
        // 易错点
        preSum[0] = 0;
        valToCount.put(0, 1);
        // 记录和为 k 的子数组个数
        int res = 0;
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
            int need = preSum[i] - k;
            if (valToCount.containsKey(need)) {
                res += valToCount.get(need);
            }
            // 将当前前缀和存入哈希表
            if (!valToCount.containsKey(preSum[i])) {
                valToCount.put(preSum[i], 1);
            } else {
                valToCount.put(preSum[i], valToCount.get(preSum[i]).intValue() + 1);
            }
        }
        return res;
    }

    /**
     * 525. 连续数组
     * https://leetcode-cn.com/problems/contiguous-array/
     * 方法：前缀和
     * 思路：此题可以等价于让找0和1数量相同的最长子数组，如果把0看成是-1，那么就等价于寻找和为0的最长子数组，即preSum[i]-preSum[j]==0
     * 相等于让去preSum数组中找i，j。使得i>j，且i-j尽可能大。
     *
     * @param nums
     * @return
     */
    public int findMaxLength(int[] nums) {
        // 计算元素的前缀和，将为0的值转换为-1
        int[] preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
        }
        // 前缀和的不重复元素和位置保存到map中
        HashMap<Integer, Integer> valToIndex = new HashMap<>();
        for (int i = 0; i < preSum.length; i++) {
            // 如果这个前缀和还没有对应的索引，则记录下来
            if (!valToIndex.containsKey(preSum[i])) {
                valToIndex.put(preSum[i], i);
            }
            // 如果这个前缀和已经有对应的索引了，则什么都不做
            // 因为题目想找长度最大的子数组，所以前缀和索引应尽可能小
        }
        // 寻找另一个值
        int len = 0;
        for (int i = 0; i < preSum.length; i++) {
            if (valToIndex.containsKey(preSum[i])) {
                int tmp = i - valToIndex.get(preSum[i]).intValue();
                if (tmp > len) {
                    len = tmp;
                }
            }
        }
        return len;
    }

    /**
     * 523. 连续的子数组和
     * https://leetcode-cn.com/problems/continuous-subarray-sum/
     * 方法：前缀和
     * 思路：计算给定数组的前缀和，(preSum[i]-preSum[j])%k==0，将前缀和与k的余数值:前缀和的元素位置保存在hashmap中，
     * 方便查找所需要的前缀和，遍历前缀和数组找到所需要的前缀和值以及其对应的元素位置，满足位置差值>=2表示存在
     *
     * @param nums
     * @param k
     * @return
     */
    // O(n)/O(n)
    public boolean checkSubarraySum(int[] nums, int k) {
        // 计算元素的前缀和
        int[] preSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        // 前缀和与k的余数值和位置保存到map中
        // 前缀和与 k 的余数到索引的映射，方便快速查找所需的前缀和
        HashMap<Integer, Integer> valToIndex = new HashMap<>();
        for (int i = 0; i < preSum.length; i++) {
            // 在哈希表中记录余数
            int val = preSum[i] % k;
            // 如果这个余数还没有对应的索引，则记录下来
            if (!valToIndex.containsKey(val)) {
                valToIndex.put(val, i);
            }
            // 如果这个前缀和已经有对应的索引了，则什么都不做，前缀和索引应尽可能小，方便我们下面查找
        }
        // 遍历前缀和数组，找到需要的前缀和以及它所在的数组位置
        for (int i = 0; i < preSum.length; i++) {
            // (preSum[i]-preSum[j])%k==0  => preSum[i]%k==need
            int need = preSum[i] % k;
            // 这个子数组的长度至少为 2
            if (valToIndex.containsKey(need) && i - valToIndex.get(need).intValue() >= 2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 304. 二维区域和检索 - 矩阵不可变
     * 方法：前缀和
     * 建立前缀和数组，第[m,n]个元素存的是[0,0]，[m-1,n-1]斜对角构成的矩阵元素之和。画图会比较简单易懂。
     */
    // O(1)/O(n^2)
    class NumMatrix {
        // 定义：preSum[i][j]记录matrix中子矩阵[0,0,i-1,j-1]的元素之和
        private int[][] preSum;

        public NumMatrix(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            if (m == 0 || n == 0) {
                return;
            }
            // 构造前缀矩阵
            preSum = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
        }
    }

    /**
     * n个数之和
     *
     * @param nums
     * @param n
     * @param start  筛选target数组的起始位置
     * @param target
     * @return
     */
    // 时间复杂度是：排序的时间复杂度为O(N^(n-1)) 空间复杂度：O(logN)
    public static List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
        // 排序
        Arrays.sort(nums);
        int length = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        // 至少是 2Sum，且数组大小不应该小于 n
        if (n < 2 || length < n) {
            return result;
        }
        // 2Sum 是 base case
        if (n == 2) {
            // 双指针那一套操作
            // 注意left=start
            int left = start, right = length - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                int leftValue = nums[left], rightValue = nums[right];
                if (sum == target) {
                    List<Integer> one = new ArrayList<>();
                    one.add(nums[left]);
                    one.add(nums[right]);
                    result.add(one);
                    // 排除相邻元素相等的情况 考虑两端
                    while (left < right && leftValue == nums[left]) {
                        left++;
                    }
                    while (left < right && rightValue == nums[right]) {
                        right--;
                    }
                } else if (sum > target) {
                    while (left < right && rightValue == nums[right]) {
                        right--;
                    }
                } else if (sum < target) {
                    while (left < right && leftValue == nums[left]) {
                        left++;
                    }
                }
            }
        } else {
            // n > 2 时，递归计算 (n-1)Sum 的结果
            // 主要这里的i=start
            for (int i = start; i < length; i++) {
                List<List<Integer>> oneList = nSum(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> element : oneList) {
                    // (n-1)Sum 加上 nums[i] 就是 nSum
                    element.add(nums[i]);
                    result.add(element);
                }
                // 排除相邻元素相等的情况
                while (i < length - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }
        return result;
    }

    /**
     * 18. 四数之和
     * https://leetcode-cn.com/problems/4sum/
     * 方法：排序+双指针
     */
    // 时间复杂度是：排序的时间复杂度为O(N^3) 空间复杂度：O(logN)
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> threeResult = threeSumList(nums, i + 1, target - nums[i]);
            for (List<Integer> element : threeResult) {
                element.add(nums[i]);
                result.add(element);
            }
            // 排除相邻元素重复的情况 注意是i+1
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return result;
    }

    private static List<List<Integer>> threeSumList(int[] nums, int start, int target) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = start; i < nums.length; i++) {
            List<List<Integer>> twoResult = twoSumList(nums, i + 1, target - nums[i]);
            for (List<Integer> element : twoResult) {
                element.add(nums[i]);
                result.add(element);
            }
            // 排除相邻元素重复的情况
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return result;
    }

    /**
     * 15. 三数之和
     * https://leetcode-cn.com/problems/3sum/
     * 方法：排序+双指针
     *
     * @param nums
     * @return
     */
    // 时间复杂度是：排序的时间复杂度为O(NlogN) 空间复杂度：O(logN)
    public static List<List<Integer>> threeSum(int[] nums) {
        // 排序
        Arrays.sort(nums);
        int target = 0;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 注意传入的start值为i+1 result不能直接赋值到这 假如使用同一个，每次循环会覆盖掉以上一次的结果
            List<List<Integer>> twoResult = twoSumList(nums, i + 1, target - nums[i]);
            for (List<Integer> element : twoResult) {
                element.add(nums[i]);
                result.add(element);
            }
            // 排除指定元素可能重复的情况
            // 这样写问题在于cur等于自身的时候也进入循环，这不能写主要原因是外层有一层循环改变i值
     /*       while (i < nums.length && cur == nums[i]) {
                i++;
            }*/
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return result;
    }

    // 计算两数之和
    private static List<List<Integer>> twoSumList(int[] nums, int start, int target) {
        int left = start, right = nums.length - 1;
        List<List<Integer>> result = new ArrayList<>();
        while (left < right) {
            int sum = nums[left] + nums[right];
            int leftValue = nums[left], rightValue = nums[right];
            if (sum == target) {
                List<Integer> one = new ArrayList<>();
                one.add(nums[left]);
                one.add(nums[right]);
                result.add(one);
                // 排除掉相邻重复的元素
                while (left < right && leftValue == nums[left]) {
                    left++;
                }
                while (left < right && rightValue == nums[right]) {
                    right--;
                }
            } else if (sum < target) {
                while (left < right && leftValue == nums[left]) {
                    left++;
                }
            } else if (sum > target) {
                while (left < right && rightValue == nums[right]) {
                    right--;
                }
            }
        }
        return result;
    }

    /**
     * 540. 有序数组中的单一元素
     * https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
     * 方法二：偶数下标的二分查找
     */
    // 时间复杂度：O(logn) 空间复杂度：O(1)
    public static int singleNonDuplicate2(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {// 不相等
            // mid的左侧是偶数个，x为奇数下标   mid为奇数：mid&1=1 mid为偶数：mid&1=0
            int mid = left + (right - left) / 2;
            mid -= mid & 1;
            if (nums[mid] == nums[mid + 1]) {// mid<x
                left = mid + 2;// 这里是+2 偶数个向后移动
            } else {// mid>=x
                right = mid;
            }
        }
        return nums[left];
    }

    /**
     * 540. 有序数组中的单一元素
     * https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
     * 方法一：全数组的二分查找
     */
    // 时间复杂度：O(logn) 空间复杂度：O(1)
    public static int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {// 不相等
            int mid = left + ((right - left) >> 1);  // 右移需要加() 这种显示使用内存不如直接除2
            if (nums[mid] == nums[mid ^ 1]) {// 相邻元素是否相等 mid<x
                left = mid + 1;
            } else {// mid>=x
                right = mid;
            }
        }
        return nums[left];
    }

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
     * 方法：二分查找
     * 思路：第一个位置leftIndex：让target-1，找到比这个值大的第一个位置。最后一个位置：rightIndex：找到比target大的第一个位置
     */
    // 时间复杂度：O(logn) 空间复杂度：O(1)
    public static int[] searchRange(int[] nums, int target) {
        // 找到比target-1大的第一个位置就是找的第一个位置
        int leftIndex = searchGtTarget(nums, target - 1);
        // 找到比target大的第一个数减1就是找的第二个位置
        int rightIndex = searchGtTarget(nums, target) - 1;
        // 排除target不在数组中的情况 注意：nums[leftIndex] == target 不是左右指针的值相等
        if (leftIndex <= rightIndex && nums[leftIndex] == target) {
            return new int[]{leftIndex, rightIndex};
        }
        return new int[]{-1, -1};
    }

    // 查找比target大的第一个位置
    private static int searchGtTarget(int nums[], int target) {
        // 注意result初始值是数组的长度，考虑数组只有一个值的情况
        int left = 0, right = nums.length - 1, result = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
                result = mid;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    /**
     * 167. 两数之和 II - 输入有序数组
     * https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
     * 方法二：双指针
     *
     * @param numbers
     * @param target
     * @return
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static int[] twoSum2(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                // 返回的是位置，不是索引值
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 167. 两数之和 II - 输入有序数组
     * https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
     * 方法一：二分查找
     * 思路：先固定左侧的一个值，target-固定值=查找的值。为避免重复查找，在右侧查询。
     *
     * @param numbers
     * @param target
     * @return
     */
    // 时间复杂度：O(nlogn) 空间复杂度：O(1)
    public static int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            // 找右侧另一个值
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                // 找右边的中位值
                int mid = (high - low) / 2 + low;
                int find = target - numbers[i];
                if (numbers[mid] == find) {
                    // 返回的是位置，不是索引值
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > find) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 12. 整数转罗马数字
     * https://leetcode-cn.com/problems/integer-to-roman/
     * 方法二：硬编码数字
     * 思路：事先定义所给定范围的罗马数字千、百、十、个位，利用模运算和除法运算
     *
     * @param num
     * @return
     */
    // 时间复杂度：O(1) 空间复杂度：O(1)
    public static String intToRoman2(int num) {
        String[] thousands = new String[]{"", "M", "MM", "MMM"};
        String[] hundreds = new String[]{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] tens = new String[]{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] ones = new String[]{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        StringBuilder roman = new StringBuilder();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();
    }


    /**
     * 12. 整数转罗马数字
     * https://leetcode-cn.com/problems/integer-to-roman/
     * 方法一：模拟（选这种吧）
     * 思路：事先定义好罗马数字对应的数字（特殊的是做减法的罗马数数字），遍历数组，传入的数字num每次减遍历值value，
     * 满足条件取当前的罗马数字，追加这个字符串
     *
     * @param num
     * @return
     */
    // 时间复杂度：O(1) 空间复杂度：O(1)
    public static String intToRoman(int num) {
        int[] storeNums = new int[]{1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        String[] storeRomons = new String[]{"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        StringBuilder stb = new StringBuilder();
        for (int i = storeNums.length - 1; i >= 0; i--) {
            int value = storeNums[i];
            // 考虑到里面拆出重复值
            while (num >= value) {
                num -= value;
                stb.append(storeRomons[i]);
            }
            if (num == 0) {
                break;
            }
        }
        return stb.toString();
    }


    /**
     * 8、字符串转换整数 (atoi)
     * 自动机：程序在每个时刻有一个状态s，每次从序列中输入一个字符c，并根据字符c转移到下一个状态s2。
     * 这个题需要把表画出来
     *
     * @param s
     * @return
     */
    public static int myAtoi(String s) {
        AutoMachine autoMachine = new AutoMachine();
        for (int i = 0; i < s.length(); i++) {
            autoMachine.getResult(s.charAt(i));
        }
        return (int) (autoMachine.sign * autoMachine.ans);
    }

    static class AutoMachine {
        private int sign = 1;// 正负标志
        private long ans = 0;// 结果值
        private String state = "start";
        private Map<String, String[]> table = new HashMap<String, String[]>() {
            {
                put("start", new String[]{"start", "signed", "inNumber", "end"});
                put("signed", new String[]{"end", "end", "inNumber", "end"});
                put("inNumber", new String[]{"end", "end", "inNumber", "end"});
                put("end", new String[]{"end", "end", "end", "end"});
            }
        };

        private void getResult(char c) {
            state = table.get(state)[getStateIndex(c)];
            if ("inNumber".equals(state)) {
                ans = ans * 10 + c - '0';
                // 取值范围判断 (long) 必须要加
                ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
            } else if ("signed".equals(state)) {
                sign = c == '+' ? 1 : -1;
            }
        }

        private int getStateIndex(char c) {
            if (c == ' ') {
                return 0;
            }
            if (c == '+' || c == '-') {
                return 1;
            }
            if (Character.isDigit(c)) {
                return 2;
            }
            return 3;
        }
    }

    /**
     * 6、Z字形变换
     * 重点之处：方向变换通过一个标志位flag转换
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        List<StringBuilder> rowsStr = new ArrayList<>();
        // 每一行都是一个字符串
        for (int i = 0; i < numRows; i++) {
            rowsStr.add(new StringBuilder());
        }
        int rowIndex = 0;
        // 到顶端（0行）、末端（numRows行）都需要换向。向下：flag=1，向上：flag=-1。因为向下行数要+1，向上行数要-1
        int flag = -1;// 这个flag用的真妙！
        for (char c : s.toCharArray()) {
            rowsStr.get(rowIndex).append(c);
            if (rowIndex == 0 || rowIndex == numRows - 1) {
                flag = -flag;
            }
            rowIndex += flag;
        }
        StringBuilder result = new StringBuilder();
        for (StringBuilder sbf : rowsStr) {
            result.append(sbf);
        }
        return result.toString();
    }

    /**
     * 5、最长回文子串
     * 解决方案：中心扩展法；动态规划
     *
     * @param s
     * @return
     */
    // 中心扩展法
    public static String longestPalindrome(String s) {
        if (null == s || s.length() < 0) {
            return s;
        }
        int left = 0;// 窗口的左指针
        int right = 0;// 窗口的右指针
        int len = 1;// 窗口的长度
        int maxLen = 0;// 窗口最大长度
        int startMax = 0;// 窗口最大长度的起始位置
        // 分两种情况：情况一：判断相邻元素是不是一样的；情况二：窗口两端的值是不是一样的
        for (int i = 0; i < s.length(); i++) {
            left = i - 1;// 左指针左移一个
            right = i + 1;// 右指针右移一个
            while (left >= 0 && s.charAt(i) == s.charAt(left)) {// 情况一
                len++;
                left--;// 继续判断左侧相邻的还有没有相同的

            }
            while (right < s.length() && s.charAt(i) == s.charAt(right)) {// 情况一
                len++;
                right++;// 继续判断右侧相邻的还有没有相同的
            }
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {// 情况二
                len = len + 2;
                left--;
                right++;
            }
            if (maxLen < len) {
                maxLen = len;
                startMax = left;
            }
            len = 1;// 没次遍历都需要将长度刷新一次
        }
        return s.substring(startMax + 1, startMax + maxLen + 1);
    }

    // 动态规划
    // 思路：长度大于2：回文串去首位之后仍旧是回文串，长度为2：只要元素相同就是回文串，长度为1：一定是回文串
    public static String longestPalindrome2(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;// 最长回文子串长度
        int startMax = 0;// 最长回文子串起始位置
        boolean[][] bp = new boolean[len][len];// 判断初始元素是否相等的结果
        // 初始化，所有长度是1的子串都是回文串
        for (int i = 0; i < len; i++) {
            bp[i][i] = true;
        }
        // 拆解首尾元素后仍未回文串，判断首尾元素是不是相同的
        for (int l = 2; l <= len; l++) {// 子串长度
            for (int i = 0; i < len; i++) {// 子串左指针
                // 确定子串的有边界 l=j-i+1;
                int j = l + i - 1;// 子串右指针
                if (j >= len) {
                    break;
                }
                if (s.charAt(i) != s.charAt(j)) {
                    bp[i][j] = false;
                } else {
                    if (j - i < 3) {// 相邻两个元素相等 踩坑 长度是要+1的
                        bp[i][j] = true;
                    } else {
                        bp[i][j] = bp[i + 1][j - 1];// 断定上一次两个元素是否相同，相同true，不相同false（重点！）
                    }
                }
                if (bp[i][j] && j - i + 1 > maxLen) {// 刷新最大长度值
                    maxLen = j - i + 1;
                    startMax = i;
                }
            }
        }
        return s.substring(startMax, startMax + maxLen);
    }

    /**
     * 3、无重复字符的最长子串
     * 解决思路：使用滑动窗口
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s) || s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map != null && map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);// 这里需要注意，左指针的位置
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}


